fonctionnement des tuples

Bonjour,

Je suis débutant en Python et j'ai un problème dans mon code que voici :

# *-coding:Utf-8 -*

class vertex:

def __init__(self, name, value):
self.name = name
self.buddies = dict()
self.value = value

def __str__(self):
return str(self.name)

class Graph:

def __init__(self, name, vertices):

self.vertices = vertices
self.name = name

def Dijkstra(G, source):

sPaths = [(float('inf'), None)]*len(G.vertices)

sPaths[source.value] = 0

pivot = source

papas = [None]*len(G.vertices)

done = []

while len(done) != (len(G.vertices)-1):
for buddy in pivot.buddies.keys():
if(sPaths[buddy.value] > sPaths[pivot.value] + pivot.buddies[buddy]):
sPaths[buddy.value] = sPaths[pivot.value] + pivot.buddies[buddy]
papas[buddy.value] = pivot
done.append(pivot)
for path in sPaths:
if path[0] == min(sPaths)[0]:
pivot = path[1]

for path in sPaths:
print("distance de "+str(source)+"à "+ str(path[1])+"= "+path[0]+"\n")

A = vertex("A", 0)
B = vertex("B", 1)
C = vertex("C", 2)
D = vertex("D", 3)
E = vertex("E", 4)
S = vertex("S", 5)

E.buddies = {A:3, B:1}
A.buddies = {E:3, B:1, C:3}
B.buddies = {E:1, A:1, C:3, D:5}
C.buddies = {A:3, B:3, D:1, S:3}
D.buddies = {B:5, C:1, S:1}


G = Graph("G", [A, B, C, D, E, S])

Dijkstra(G,E)

Le rapport d'erreur est le suivant :

File "Dijkstra.py", line 61, in <module>
Dijkstra(G,E)
File "Dijkstra.py", line 39, in Dijkstra
if path[0] == min(sPaths)[0]:
TypeError: 'int' object has no attribute '__getitem__'

Je suis désolé par avance si la solution est évidente mais j'ai fait des tests intermédiaires et a priori la méthode min renvoie bien un tuple alors je ne comprends pas pourquoi min(sPaths)[0] renvoie une erreur. Merci à tous ceux qui prendront le temps de réfléchir à mon problème.

Cordialement

Citation:

---

Envoyé par ImmoTPA

Je suis désolé par avance si la solution est évidente mais j'ai fait des tests intermédiaires et a priori la méthode min renvoie bien un tuple alors je ne comprends pas pourquoi min(sPaths)[0] renvoie une erreur. Merci à tous ceux qui prendront le temps de réfléchir à mon problème.

---

Une valeur minimum étant par définition unique, il n'y a pas de bonne raison pour que "min" retourne autre chose qu'une valeur.
Après la fonction "min" de Python pourrait inventer autre chose mais elle ne fera que ce qui est documenté:

Code:

---

1 2 3 4 5 6 7 8 9 10 11

>>> help(min) Help on built-in function min in module builtins:   min(...) min(iterable[, key=func]) -> value min(a, b, c, ...[, key=func]) -> value   With a single iterable argument, return its smallest item. With two or more arguments, return the smallest argument.   >>>

---

- W

Bonjour wiztricks,

Je te remercie de ta réponse, par ailleurs je ne comprends pas. Voici le résultat du code suivant que j'ai écrit dans un fichier test :

sPaths = [(float('inf'), None)]*len(G.vertices)
sPaths[1] = (12, A)
a = min(sPaths)
print(a)

(12, <__main__.vertex instance at 0x7fa91e37ec20>)

et donc voici ce que j'obtiens quand j'écris cela :

a = min(sPaths)
print(a[1])
print(a[0])

A
12

Donc au final je crois que min renvoie le tuple minimal au sens du premier argument, ici ce sont des distances donc mon plus petit tuple au sens de la distance est bien celui proposé et pourtant pas moyen de faire la comparaison entre le premier argument de ce tuple qui est un int et un autre int. Si tu vois ce qui m'échappe je t'en prie...En te remerciant à nouveau de te pencher sur mon problème.

Ce n'est probablement pas là

Code:

---

....... == min(sPaths)[0]:

---

que ça coince mais là:

Code:

---

if path[0] == ...

---

Et pourquoi donc ?

Parce que tu as réutilisé le nom path dans une boucle plus avant, là:

Code:

---

1 2	for path in sPaths:

---

... et ouais.

Prenez un truc bizarre comme:

Code:

---

1 2 3 4

>>> paths = [ (ord(_),_) for _ in 'abcde' ] >>> paths [(97, 'a'), (98, 'b'), (99, 'c'), (100, 'd'), (101, 'e')] >>>

---

"min" osera vous retourner quelque chose:

Code:

---

1 2 3

>>> min(paths) (97, 'a') >>>

---

Et il est "consistent" avec lui même:

Code:

---

1 2 3

>>> paths.reverse() >>> min(paths) (97, 'a')

---

Pour ce faire, il utilise une sorte de diversion: les objets ayant un id unique, retournons l'objet qui a le plus petit id.

Code:

---

1 2 3 4 5 6 7 8

>>> for e in paths: ... print (e, id(e)) ... (101, 'e') 42830856 (100, 'd') 45304520 (99, 'c') 45215880 (98, 'b') 45303496 (97, 'a') 45303304

---

Que dire? garbage in garbage out...

- W

Merci pour vos réponses. Par contre Vinsz j'aimerai bien que vous m'expliquiez le problème. Si path n'était pas dans la boucle comment pourrais-je m'en servir ?

Citation:

---

Envoyé par ImmoTPA

Merci pour vos réponses. Je vais essayer d'override min alors. Par contre Vinsz j'aimerai bien que vous m'expliquiez le problème. Si path n'était pas dans la boucle comment pourrais-je m'en servir ?

---

Il serait sage de reposter votre code avec la balise "code" pour respecter les indentations, sinon on racontera ce qu'on peut sur le reste mais c'est "au pif".

- W

Citation:

---

Envoyé par wiztricks

Prenez un truc bizarre comme:

Code:

---

1 2 3 4

>>> paths = [ (ord(_),_) for _ in 'abcde' ] >>> paths [(97, 'a'), (98, 'b'), (99, 'c'), (100, 'd'), (101, 'e')] >>>

---

"min" osera vous retourner quelque chose:

Code:

---

1 2 3

>>> min(paths) (97, 'a') >>>

---

Pour ce faire, il utilise une sorte de diversion: les objets ayant un id unique, retournons l'objet qui a le plus petit id.

Code:

---

1 2 3 4 5 6 7 8

>>> for e in paths: ... print (e, id(e)) ... (101, 'e') 42830856 (100, 'd') 45304520 (99, 'c') 45215880 (98, 'b') 45303496 (97, 'a') 45303304

---

Que dire? garbage in garbage out...

- W

---

Parce qu'évidemment 45_303_304 (id de (97, 'a')) < 42_830_856 (id de (101, 'e')) ?:roll:
Ah tiens, non ?
Peut-être finalement que min() est défini en fonction de l'ordre donné par les comparaisons... Et je suis relativement sûr que les comparaisons sont définies sur les tuples avec l'ordre classique sur les tuples : l'ordre lexicographique (celui du dictionnaire). Ça serait un peu gros que Python, qui se veut fortement typé fasse ce genre de comparaisons bidons sur des objets aussi souvent utilisés que les tuples.

Code:

---

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 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61

# *-coding:Utf-8 -*   class vertex:   def __init__(self, name, value): self.name = name self.buddies = dict() self.value = value   def __str__(self): return str(self.name)   class Graph:   def __init__(self, name, vertices):   self.vertices = vertices self.name = name   def Dijkstra(G, source):   sPaths = [(float('inf'), None)]*len(G.vertices)   sPaths[source.value] = 0   pivot = source   papas = [None]*len(G.vertices)   done = []   while len(done) != (len(G.vertices)-1): for buddy in pivot.buddies.keys(): if(sPaths[buddy.value] > sPaths[pivot.value] + pivot.buddies[buddy]): sPaths[buddy.value] = sPaths[pivot.value] + pivot.buddies[buddy] papas[buddy.value] = pivot done.append(pivot) for path in sPaths: if path[0] == min(sPaths)[0]: pivot = path[1]   for path in sPaths: print("distance de "+str(source)+"à "+ str(path[1])+"= "+path[0]+"\n")   A = vertex("A", 0) B = vertex("B", 1) C = vertex("C", 2) D = vertex("D", 3) E = vertex("E", 4) S = vertex("S", 5)   E.buddies = {A:3, B:1} A.buddies = {E:3, B:1, C:3} B.buddies = {E:1, A:1, C:3, D:5} C.buddies = {A:3, B:3, D:1, S:3} D.buddies = {B:5, C:1, S:1}     G = Graph("G", [A, B, C, D, E, S])   Dijkstra(G,E)

---

Désolé c'est vrai que j'aurai du y penser avant je ne connaissais pas l'existence de cette balise. Merci

Bonjour Jedai,

Merci pour ta réponse, as tu une idée du problème ?

Citation:

---

Envoyé par ImmoTPA

Merci pour ta réponse, as tu une idée du problème ?

---

Si tu codes dans un langage dynamiquement typé, il faut prêter grande attention au type de tes objets, et quand tu as une structure à deux niveaux, il faut faire attention à ne pas en oublier 1, par exemple :

Code:

---

1 2 3

sPaths = [(float('inf'), None)]*len(G.vertices)   sPaths[source.value] = 0

---

D'un côté sPaths est une liste de Tuples, de l'autre côté tu affecte à l'un de ses éléments (un tuple à l'origine) la valeur 0 (un entier)...
Tu fais plusieurs erreurs similaires par la suite.

--
Jedaï

En effet je n'avais pas vu ça merci. J'essaie de corriger mes erreurs.

En fait ta principale erreur semble être que tu hésites entre des sommets numérotés et des sommets nommés... Du coup ton sPaths est plus compliqué que nécessaire (tu es censé stocker le sommet de destination dans la seconde composante de tes tuples, mais tu les laisses à None...) et tu n'arrêtes pas d'écrire ton code comme si sPaths était un tableau d'entiers. Je te conseille de choisir un modèle et de t'y tenir : soit tes sommets ont des noms et tes structures de données devraient pratiquement toute être des dictionnaires, soit ils sont numérotés implicitement à la création du graphe et tu n'as pas besoin de stocker leur numéro dans le sommet, juste leur nom et voisins.

Grâce à ta réponse j'en suis là.

Code:

---

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 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61

# *-coding:Utf-8 -*   class vertex:   def __init__(self, name, value): self.name = name self.buddies = dict() self.value = value   def __str__(self): return str(self.name)   class Graph:   def __init__(self, name, vertices):   self.vertices = vertices self.name = name   def Dijkstra(G, source):   sPaths = [(float('inf'), None)]*len(G.vertices)   sPaths[source.value] = (0, source)   pivot = source   papas = [None]*len(G.vertices)   done = []   while len(done) != (len(G.vertices)-1): for buddy in pivot.buddies.keys(): if(sPaths[buddy.value][0] > sPaths[pivot.value][0] + pivot.buddies[buddy][0]): sPaths[buddy.value][0] = sPaths[pivot.value][0] + pivot.buddies[buddy][0] papas[buddy.value][1] = pivot done.append(pivot) for path in sPaths: if path[0] == min(sPaths)[0]: pivot = path[1]   for path in sPaths: print("distance de "+str(source)+"à "+ str(path[1])+"= "+path[0]+"\n")   A = vertex("A", 0) B = vertex("B", 1) C = vertex("C", 2) D = vertex("D", 3) E = vertex("E", 4) S = vertex("S", 5)   E.buddies = {A:3, B:1} A.buddies = {E:3, B:1, C:3} B.buddies = {E:1, A:1, C:3, D:5} C.buddies = {A:3, B:3, D:1, S:3} D.buddies = {B:5, C:1, S:1}     G = Graph("G", [A, B, C, D, E, S])   Dijkstra(G,E)

---

J'ai le sentiment d'avoir respecter le type de mes objets et pourtant il n'accepte toujours pas les comparaisons de mon premier argument dans mes tuples (qui sont int). J'obtiens ce message d'erreur.

File "Dijkstra.py", line 61, in <module>
Dijkstra(G,E)
File "Dijkstra.py", line 34, in Dijkstra
if((sPaths[buddy.value])[0] > (sPaths[pivot.value])[0] + (pivot.buddies[buddy])[0]):
TypeError: 'int' object has no attribute '__getitem__'

Merci encore de ton aide.

(pivot.buddies[buddy]) est déjà un entier (car pivot.buddies est un dictionnaire d'entiers).

Vu avec l'indentation le code m'apparaît différemment, mais il reste possible que l'erreur soit dans

Code:

---

1 2

path[0]

---

du fait du code qui précède.

Tu te simplifierais la vie en printant des données:

Code:

---

1 2 3

for path in sPaths: print path[0], sPath

---

J'ai fait le print que tu m'as conseillé. Auparavant j'ai pu corriger mes erreurs de syntaxe puisque maintenant mon programme s'execute mais je dois avoir une erreur car la console m'affiche ceci :

177180
inf
inf
inf
inf
inf
177181
inf
inf
inf

à l'infini...

Je dois avoir une erreur de raisonnement dans mes boucles.

Ah nan je suis juste stupide, comme tu me l'as fait remarqué j'ai laissé mes sommets de mes tuples à None donc je ne risquais pas d'y arriver.

Citation:

---

Envoyé par Jedai

Peut-être finalement que min() est défini en fonction de l'ordre donné par les comparaisons... Et je suis relativement sûr que les comparaisons sont définies sur les tuples avec l'ordre classique sur les tuples : l'ordre lexicographique (celui du dictionnaire). Ça serait un peu gros que Python, qui se veut fortement typé fasse ce genre de comparaisons bidons sur des objets aussi souvent utilisés que les tuples

---

Tout à fait, tuple et list sont comparés "lexicographiquement", merci de le rappeler.

Mon propos était de dire qu'il ne suffisait pas de passer à "min" n'importe quoi et d'espérer qu'il s'en débrouille.

La solution sera dans ce cas sera d'écrire:

Code:

---

1 2 3

for path in sPaths: if path[0] == min(sPaths, key=lambda e: e[0])[0]: pivot = path

---

i.e. préciser l'indice de la valeur à comparer.

Mais c'est vrai qu'il y a d'autres "incohérences" à corriger avant.

- W

Merci wiztricks. En effet ton code semble mieux fonctionner que le mien. Néanmoins lorsque je lance mon programme celui ci tourne à l'infini et lorsque je l'arrête au clavier j'ai ceci :

File "Dijkstra.py", line 60, in <module>
Dijkstra(G,E)
File "Dijkstra.py", line 38, in Dijkstra
if path[0] == min(sPaths, key=lambda e: e[0])[0]:
KeyboardInterrupt

Je ne sais pas si cela signifie que le programme plante à cet endroit là ou non.

Voici mon code

Code:

---

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 47 48 49 50 51 52 53 54 55 56 57 58 59 60

# *-coding:Utf-8 -*   class vertex:   def __init__(self, name, value): self.name = name self.buddies = dict() self.value = value   def __str__(self): return str(self.name)   class Graph:   def __init__(self, name, vertices):   self.vertices = vertices self.name = name   def Dijkstra(G, source):   sPaths = [(float('inf'), vertex) for vertex in G.vertices] sPaths[source.value] = (0, source)   pivot = source   papas = [None]*len(G.vertices)   done = []   while len(done) != (len(G.vertices)-1): for buddy in pivot.buddies.keys(): if(sPaths[buddy.value][0] > sPaths[pivot.value][0] + pivot.buddies[buddy]): sPaths[buddy.value] = (sPaths[pivot.value][0] + pivot.buddies[buddy], sPaths[buddy.value][1]) papas[buddy.value] = pivot done.append(pivot) for path in sPaths: if path[0] == min(sPaths, key=lambda e: e[0])[0]: pivot = path[1]   for path in sPaths: print("distance de "+str(source)+"à "+ str(path[1])+"= "+path[0]+"\n")   A = vertex("A", 0) B = vertex("B", 1) C = vertex("C", 2) D = vertex("D", 3) E = vertex("E", 4) S = vertex("S", 5)   E.buddies = {A:3, B:1} A.buddies = {E:3, B:1, C:3} B.buddies = {E:1, A:1, C:3, D:5} C.buddies = {A:3, B:3, D:1, S:3} D.buddies = {B:5, C:1, S:1}     G = Graph("G", [A, B, C, D, E, S])   Dijkstra(G,E)

---

Merci à tous de votre intérêt.

Citation:

---

Envoyé par wiztricks

Tout à fait, tuple et list sont comparés "lexicographiquement", merci de le rappeler.

Mon propos était de dire qu'il ne suffisait pas de passer à "min" n'importe quoi et d'espérer qu'il s'en débrouille.

La solution sera dans ce cas sera d'écrire:

Code:

---

1 2 3

for path in sPaths: if path[0] == min(sPaths, key=lambda e: e[0])[0]: pivot = path

---

i.e. préciser l'indice de la valeur à comparer.

---

Certes un utile bout de code mais ici inutile puisque l'ordre lexicographique commence par comparer les valeurs au premier indice.

Citation:

---

Envoyé par wiztricks

Mais c'est vrai qu'il y a d'autres "incohérences" à corriger avant.

---

Je pense que tout cela est lié : sPaths semble être une liste d'entiers (de distances) indexée par les numéros des sommets de destination dans une grande partie du code de ImmoTPA... Finalement cette histoire de tuple est peut-être aussi inutile que créatrice de confusion. La première chose à faire serait probablement de s'accorder pour dire que dans Dijkstra, et à part pour l'affichage, le seul "nom" des sommets qui compte est leur indice dans vertices.

--
Jedaï

Citation:

---

Envoyé par Jedai

Certes un utile bout de code mais ici inutile puisque l'ordre lexicographique commence par comparer les valeurs au premier indice.

---

Il n'est jamais inutile d'être trop précis.

Citation:

---

Je pense que tout cela est lié : sPaths semble être une liste d'entiers (de distances) indexée par les numéros des sommets de destination dans une grande partie du code de ImmoTPA... Finalement cette histoire de tuple est peut-être aussi inutile que créatrice de confusion. La première chose à faire serait probablement de s'accorder pour dire que dans Dijkstra, et à part pour l'affichage, le seul "nom" des sommets qui compte est leur indice dans vertices.

---

Laissez ImmoTPA suivre son idée, elle est compliquée, il va en ch...
Mais s'il arrive à mettre au point son truc, il pourra en être fier. Dans quelques mois, il aura peut être l'occasion de relire son code et il se demandera sans doute qu'est ce qu'il avait bien pu fumer le jour ou il a écrit çà.

- W

Citation:

---

Envoyé par wiztricks

Il n'est jamais inutile d'être trop précis.

---

Particulièrement ici vu que vertex n'est pas ordonné...

Citation:

---

Envoyé par wiztricks

Laissez ImmoTPA suivre son idée, elle est compliquée, il va en ch...
Mais s'il arrive à mettre au point son truc, il pourra en être fier. Dans quelques mois, il aura peut être l'occasion de relire son code et il se demandera sans doute qu'est ce qu'il avait bien pu fumer le jour ou il a écrit çà.

---

Parfaitement, à partir du moment où il suit son idée, une seule idée pas un mélange de deux idée partiellement compatibles :)

Un détail toutefois pour éviter à ImmoTPA de tourner en rond :

Code:

---

1 2 3 4

done.append(pivot) for path in sPaths: if path[0] == min(sPaths, key=lambda e: e[0])[0]: pivot = path[1]

---

Ces deux lignes sont mal indentés (tu veux qu'ils s'exécutent une fois par tour de la boucle while, pas de la boucle for).
Par ailleurs tu ne veux pas choisir deux fois le même pivot, la liste done peut servir.

Oui j'ai remarqué ça merci, la dernière chose à faire pour que ça fonctionne est de comparer le path de chaque sommet au path minimal pour choisir le nouveau pivot, sauf qu'il faut comparer aux paths de tous les sommets sauf des sommets de done. Ce que j'ai essayé de diverses manières dont celle-ci :

Code:

---

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 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68

# *-coding:Utf-8 -*   class vertex:   def __init__(self, name, value): self.name = name self.buddies = dict() self.value = value   def __str__(self): return str(self.name)   class Graph:   def __init__(self, name, vertices):   self.vertices = vertices self.name = name   def Dijkstra(G, source):   sPaths = [(float('inf'), vertex) for vertex in G.vertices]   sPaths[source.value] = (0, source)   pivot = source   papas = [None]*len(G.vertices)   done = []   while len(done) != (len(G.vertices)-1):   done.append(pivot) for i in done: print str(i)+"\n" for buddy in pivot.buddies.keys():   if(sPaths[buddy.value][0] > sPaths[pivot.value][0] + pivot.buddies[buddy]): sPaths[buddy.value] = (sPaths[pivot.value][0] + pivot.buddies[buddy], sPaths[buddy.value][1]) papas[buddy.value] = pivot   copie = list(sPaths) del copie[min(sPaths, key=lambda e: e[0])[0]]   for sommet in set([t[1] for t in copie])-set(done): if sPaths[sommet.value][0] == min(copie, key=lambda e: e[0])[0]: pivot = sommet   for path in sPaths: print("distance de "+str(source)+" à "+ str(path[1])+" = "+str(path[0])+"\n")   A = vertex("A", 0) B = vertex("B", 1) C = vertex("C", 2) D = vertex("D", 3) E = vertex("E", 4) S = vertex("S", 5)   E.buddies = {A:3, B:1} A.buddies = {E:3, B:1, C:3} B.buddies = {E:1, A:1, C:3, D:5} C.buddies = {A:3, B:3, D:1, S:3} D.buddies = {B:5, C:1, S:1}     G = Graph("G", [A, B, C, D, E, S])   Dijkstra(G,E)

---

mais qui ne fonctionne pas, E reste mon pivot du début à la fin. Je vais prendre en compte vos remarques pour voir si je trouve d'où cela vient.

Voici le code qui fonctionne. Je clos la discussion, merci de votre aide.

Code:

---

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 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69

# *-coding:Utf-8 -*   class vertex:   def __init__(self, name, value): self.name = name self.buddies = dict() self.value = value   def __str__(self): return str(self.name)   class Graph:   def __init__(self, name, vertices):   self.vertices = vertices self.name = name   def Dijkstra(G, source):   sPaths = [(float('inf'), vertex) for vertex in G.vertices]   sPaths[source.value] = (0, source)   pivot = source   papas = [None]*len(G.vertices)   done = []     while len(done) != (len(G.vertices)-1):   print str(pivot) done.append(pivot)   for buddy in pivot.buddies.keys(): if(sPaths[buddy.value][0] > sPaths[pivot.value][0] + pivot.buddies[buddy]): sPaths[buddy.value] = (sPaths[pivot.value][0] + pivot.buddies[buddy], sPaths[buddy.value][1]) papas[buddy.value] = pivot       for sommet in set([t[1] for t in sPaths])-set(done): if sPaths[sommet.value][0] == min(set([t[0] for t in sPaths])-set(sPaths[i.value][0] for i in done)): pivot = sommet     for path in sPaths: print("distance de "+str(source)+" à "+ str(path[1])+" = "+str(path[0])+"\n")   A = vertex("A", 0) B = vertex("B", 1) C = vertex("C", 2) D = vertex("D", 3) E = vertex("E", 4) S = vertex("S", 5)   E.buddies = {A:3, B:1} A.buddies = {E:3, B:1, C:3} B.buddies = {E:1, A:1, C:3, D:5} C.buddies = {A:3, B:3, D:1, S:3} D.buddies = {B:5, C:1, S:1}     G = Graph("G", [A, B, C, D, E, S])   Dijkstra(G,E)

---

Juste pour indication, quand je disais qu'il valait mieux rester avec un seul système de désignation des sommets, je voulais dire quelque chose comme cela :

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19

def Dijkstra(G, source): dists = {v:float('inf') for v in G.vertices} ancestor = {v:None for v in G.vertices} todo = set(G.vertices) dists[source] = 0   while todo: # still not empty by = min(todo, key=lambda v: dists[v])   for (to, dist) in by.buddies.items(): distBy = dists[by] + dist if dists[to] > distBy: dists[to] = distBy ancestor[to] = by   todo.discard(by)   for target in G.vertices: print("Distance de " + str(source) + " à " + str(target) + " = " + str(dists[target]) + "\n")

---

--
Jedaï