Discussion :

[Jedai]

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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.

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ï

[wiztricks]

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.

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

[Jedai]

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

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

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

[Jedai]

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

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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.

[ImmoTPA]

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 :

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
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.

[ImmoTPA]

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

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
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)

[Jedai]

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 :

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
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ï