Bonjour,

J'essaye de coder en python l'algorithme de Prim qui permet d'obtenir l'arbre couvrant minimal dans un graphe connexe.

Malheureusement, j'obtiens une erreur que je n'arrive pas à résoudre :

[(1, 0)]
Traceback (most recent call last):
File "/Users/Moi/CX/Python/Graphe/primtest.py", line 46, in <module>
Prim(Graphe1)
File "/Users/Moi/CX/Python/Graphe/primtest.py", line 18, in Prim
if ((min and distanceMin[j] and 0 <= distanceMin[j] < min) or (not min and 0 <= distanceMin[j])):
TypeError: unorderable types: int() <= NoneType()
[Finished in 0.1s with exit code 1]
Voici mon code :

Code : Sélectionner tout - Visualiser dans une fenêtre à part
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
def Prim (Graphe):
  T = []
  n = len(Graphe)
  plusProche = []
  distanceMin = []
 
  for i in range(0,n):
    plusProche.append(0)
    distanceMin.append(0)
 
  for i in range(1,n):
    plusProche[i] = 0
    distanceMin[i] = Graphe[i][0]
 
  for i in range(0,n-1):
    min = None
    for j in range(1,n):
      if ((min and distanceMin[j] and 0 <= distanceMin[j] < min) or (not min and  0 <= distanceMin[j])):
        min = distanceMin[j]
        k = j
 
    T.append((k, plusProche[k]))
    print(T)
 
    distanceMin[k] = -1
    distanceMin[plusProche[k]] = -1
 
    for j in range(1,n):
      if ((distanceMin[j] and Graphe[k][j] and Graphe[k][j] < distanceMin[j]) or not distanceMin[j] ):
        distanceMin[j] = Graphe[k][j]
        distanceMin[k] = Graphe[j][k]
 
        plusProche[j] = k
        plusProche[k] = j
 
  return T
 
Graphe1 = [[None, 1, None, 4, None, None, None],
[1, None, 2, 6, 4, None, None],
[None, 2, None, None, 5, 6, None],
[4, 6, None, None, 3, None, 4],
[None, 4, 5, 3, None, 8, 7],
[None, None, 6, None, 8, None, 3],
[None, None, None, 4, 7, 3, None]]
 
Prim(Graphe1)
Pouvez-vous m'aider ?

Merci d'avance.

PS : je suis sous python 3.3.2