Bonsoir, (ou re pour ceux qui m'ont déjà vu)

Déjà premièrement, oui je suis en train de travailler sur les graphes, je suis en train de faire l'algorithme de Dijkstra.

Je rencontre un problème, en effet, mon dictionnaire distance ne veut pas changer les valeurs on dirait.

Voici le code:

def dij(G, s0, s1):
    couleur = {couleur:'white' for couleur in G.adjacent}
    distance = {distance:(9999, None) for distance in G.adjacent}
    couleur[s0] = "red"
    distance[s0] = (0, None)
    for v in G.voisins(s0):
        if couleur[v] == "white" or couleur[v] == "grey":
            couleur[v] == "grey"
        elif distance[v][0] > distance[s0][0] + G.poids[(s0, v)]:
            distance[v][0] > distance[s0][0] + G.poids[(s0, v)]
            distance[v] = (distance[v][0], s0)
        return couleur, distance

Ici, G.adjacent correspond à un graphe dont uniquement un sommet est la clé d'une valeur, qui sont ses sommets adjacents. Exemple, G = {A: ['B', 'C'}

G.poids a comme clé un tuple et sa valeur est son poids. Exemple, G = {('A', 'B'): 2}

La méthode voisins détermine les voisins du sommet soit les valeurs de la clé insérée. 

Le problème ici, c'est que je n'arrive pas a changer les valeurs des distances, et je n'arrive pas à détecter le problème dans les lignes 9 à 11. Les distances restent à 9999, None alors que je change la valeur des voisins de s0, sommet de départ.

pas mal de choses qui ne vont pas dans ton code :

• ton return ligne 12 est très probablement prématuré (et donc algorithmiquement incorrect)
• ta ligne 10 est comme du code mort (ou alors c'est une erreur de copier-coller)
• on aurait dit que le test ligne 9 devrait plutôt être un strictement inférieur mais difficile de dire vu l'absence de contexte.

PascalOrtiz a écrit:

pas mal de choses qui ne vont pas dans ton code :

• ton return ligne 12 est très probablement prématuré (et donc algorithmiquement incorrect)
• ta ligne 10 est comme du code mort (ou alors c'est une erreur de copier-coller)
• on aurait dit que le test ligne 9 devrait plutôt être un strictement inférieur mais difficile de dire vu l'absence de contexte.

Bonjour, 

Oui en effet sans faire exprès j'ai mal copié collé, du coup le test à la ligne 9 est plutôt si distance[v][0] > distance[s0][0] + G.poids[(s0, v)], alors distance[v][0] = distance[s0][0] + G.poids[(s0, v)]

Cette ligne correspond au tableau à la ligne où on remplace l'infini (ici j'ai mis 9999) par la distance de 0 dans le dictionnaire plus celle qu'on trouve dans le graphe pondéré. 

Et également, le return est à cet emplacement car j'ai déjà fini le pseudo-code, c'est juste la retranscription qui me pose problème et donc je divise le code en parties pour bien si ça fait bien les étapes.

Voici le code en entier si vous voulez:

def dij(G, s0, s1):
    couleur = {couleur:'white' for couleur in G.adjacent}
    distance = {distance:(9999, None) for distance in G.adjacent}
    couleur[s0] = "red"
    distance[s0] = (0, None)
    while s0 != s1:
        for v in G.voisins(s0):
            if couleur[v] == "grey" or couleur[v] == "white":
                couleur[v] ==  "grey"
            elif distance[v][0] > distance[s0][0] + G.poids(s0, v):
                distance[v][0] = distance[s0][0] + G.poids(s0, v)
                distance[v] = (distance[v][0], s0)
        l = []
        for i in distance.keys():
            l.append(distance[i][0])
            if distance[i][1] == None or distance[i][1] != s0:
                l.remove(distance[i][0])
        return distance, couleur, l
        petite_valeur = min(l)
        petit_sommet = [k for k, val in distance.items() if val == (petite_valeur, s0)]
        petit_sommet = s0
        couleur[s0] = 'red'

    while couleur[s1] != "red":
        petit_sommet = s0
        couleur[petit_sommet] = "red"
        for j in G.voisins(s0):
            if couleur[v] == "white":
                couleur[v] == "grey"

    return couleur, distance, petit_sommet

return fait sortir de la fonction, donc tout ce qui est derrière ne sera pas exécuté

passe par une variable intermédiaire, ou fait le calcule directement

distance[v] = (distance[s0][0] + G.poids(s0, v),s0)

on ne peut pas modifier un élément d'un tuple

Les lignes couleur[v] == "grey" sont aussi du code mort.