Bellman-Ford - Récupérer les sommets du plus court chemin

[Evanou]

Bonjour !
Je suis étudiant en M1 maths appliquées et je rencontre une difficulté dans la rédaction de mon mémoire. Je dois coder (en python) un algorithme de plus court chemin, ayant étudié en cours la partie théorique de la programmation dynamique ( principe de Bellman) je me suis lancé sur un algo de Bellman-Ford. Cela me paraît pertinent pour faire écho à mes cours même si le graphe que je considère n'a pas de pondération négative...

Mon code semble fonctionner (même s'il n'est pas très beau) mais je ne parviens pas à récupérer la liste totale des sommets composant les dits plus courts chemins calculés : Je n'ai que le début et la plus petite distance ! Comment récupérer la totalité de ces listes ?
(désolé pour la longueur du post )
Voici mon code test sur un graphe simple (je souhaite étudier le métro parisien à terme), soyez indulgents

Code: Tout sélectionner

import numpy as np
import math
mat = np.array( [[0,1,0,0,0,0,0,1],
                 [1,0,1,0,0,0,0,1],
                 [0,1,0,1,0,0,0,0],
                 [0,0,1,0,1,1,0,1],
                 [0,0,0,1,0,1,0,0],
                 [0,0,0,1,1,0,1,0],
                 [0,0,0,0,0,1,0,1],
                 [1,0,0,1,0,0,1,0]])

src = 0
L = [math.inf] * len(mat)
P = [math.inf] * len(mat)
L[src] = 0
P[src] = src
go = True
list_path = np.ones((len(mat),len(mat)))
list_path = math.inf * list_path
edgelist = []

for i in range(0,len(mat)):
    for j in range(0,len(mat)):
            if mat[i][j] == 1:
                edge = (i,j)
                edgelist.append(edge)


i = 0
while go == True:
    go = False
    for (x,y) in edgelist:
        list_path[y][0] = y
        if L[y] > L[x] + mat[x][y]:
             L[y] = L[x] + mat[x][y]
             P[y] = x
             go = True
        list_path[y][i] = P[y]
        i = + 1
       

print('P=',P)
print('L=',L)
print('list_path=',list_path )


et la sortie :

Code: Tout sélectionner

P= [0, 0, 1, 7, 3, 3, 7, 0]
L= [0, 1, 2, 2, 3, 3, 2, 1]
list_path= [[ 0.  0. inf inf inf inf inf inf]
 [ 1.  0. inf inf inf inf inf inf]
 [ 2.  1. inf inf inf inf inf inf]
 [ 3.  7. inf inf inf inf inf inf]
 [ 4.  3. inf inf inf inf inf inf]
 [ 5.  3. inf inf inf inf inf inf]
 [ 6.  7. inf inf inf inf inf inf]
 [ 7.  0. inf inf inf inf inf inf]]


[L.A.]

Bonjour,

j'ai un doute sur le "i+=1" que tu mets dans ta boucle "for", ne faut-il pas plutôt le sortir et le mettre seulement dans la boucle "while" ?
D'ailleurs si tu affiches aussi i après exécution, est-ce que ça donne ce que tu attends ?
(petit conseil, pour trouver les erreurs, n'hésite pas à rajouter des print provisoires dans l'algo pour voir ce qu'il fait à chaque étape)
Et tel que c'est écrit "i = +1", i prend seulement la valeur 1, donc forcément ton tableau list_path ne se remplit qu'à la première colonne.
J'ai remarqué aussi que ta matrice n'est pas symétrique : en 2e ligne dernière colonne il y a 1, en dernière ligne 2e colonne il y a 0.

[Evanou]

Merci pour la réponse rapide !

Oui j'ai effacé les 100 prints du code pour que vous y voyez plus clair !
-j'ai essayé le "i=+1" seulement dans le "while", puis dans le "for", puis dans le "if", avec un print i à la sortie de la boucle, dans les 3 cas j'ai:

Code: Tout sélectionner

i= 1
P= [0, 0, 1, 7, 3, 3, 7, 0]
L= [0, 1, 2, 2, 3, 3, 2, 1]
list_path= [[ 0.  0. inf inf inf inf inf inf]
 [ 1.  0. inf inf inf inf inf inf]
 [ 2.  1. inf inf inf inf inf inf]
 [ 3.  7. inf inf inf inf inf inf]
 [ 4.  3. inf inf inf inf inf inf]
 [ 5.  3. inf inf inf inf inf inf]
 [ 6.  7. inf inf inf inf inf inf]
 [ 7.  0. inf inf inf inf inf inf]]

Non ma matrice n'est pas symétrique, j'ai lu que Bellman-Ford est censé fonctionner sur des graphes quelconques, c'est faux ?

[Evanou]

j'ai en effet oublié un 1 dans ma matrice, sinon ce serait un graphe orienté c'est ça !? désolé pour la coquille
Mais ça ne fonctionne pas plus

[L.A.]

-j'ai essayé le "i=+1" seulement dans le "while", puis dans le "for", puis dans le "if",

attention c'est "i += 1" (équivalent de "i = i+1") et non pas "i = +1" (équivalent de "i=1").

[Evanou]

Voici, (avec les moyens du bords) mon graphe !
*********** 4
********* / \
2------- 3 -----5
| ***** * | ***** |
1------- 7 ----- 6
* \ ****/
*** 0

J'ai corrigé le" i = i +1", j'ai donc ce code:

Code: Tout sélectionner

i = 0
while go == True:
    go = False
    i += 1
    for (x,y) in edgelist:
        list_path[y][0] = y
        if L[y] > L[x] + mat[x][y]:
             L[y] = L[x] + mat[x][y]
             P[y] = x
             go = True

        list_path[y][i] = P[y]


avec une nouvelle sortie:

Code: Tout sélectionner

i= 3
P= [0, 0, 1, 7, 3, 3, 7, 0]
L= [0, 1, 2, 2, 3, 3, 2, 1]
list_path= [[ 0.  0.  0.  0. inf inf inf inf]
 [ 1.  0.  0.  0. inf inf inf inf]
 [ 2.  1.  1.  1. inf inf inf inf]
 [ 3.  7.  7.  7. inf inf inf inf]
 [ 4.  3.  3.  3. inf inf inf inf]
 [ 5.  3.  3.  3. inf inf inf inf]
 [ 6.  7.  7.  7. inf inf inf inf]
 [ 7.  0.  0.  0. inf inf inf inf]]


Le nœud numéro deux de chaque chemin se répète ! C'est un peu du bricolage, mais si je veux connaitre le chemin optimal de 4 à 0 par exemple. Là avec cette sortie je sais que le "premier bout du chemin" est 4-->3, je sais aussi que le chemin optimal de 3 à 0, c'est 3-->7 et donc on a bien 4,3,7,0. Est-ce que je peux, "coller" les lignes de ma matrices en bidouillant et si oui est ce que c'est transposable à un plus grand graphe ... pondéré ?

[L.A.]

list_path[y][i] = P[y]

C'est donc là que ça coince...
P[y] est sensé être l'avant dernier sommet dans le chemin le plus court de 0 à y, mais il n'a pas de rapport avec le reste du chemin. Il faudrait plutôt écrire quelque chose du genre :

Code: Tout sélectionner

list_path[y][i] = P[int(list_path[y][i-1])]

Mais ce qui me gène aussi, c'est que P évolue en permanence avant de se stabiliser, donc les chemins construits avec un P qui n'est pas le P définitif sont faux...
Je ne sais pas si c'est possible de le faire comme tu fais. Pour ma part j'éliminerais cette ligne (c'est possible car on n'utilise nulle part ailleurs la variable list_path) et je ferais un deuxième algorithme pour reconstruire les chemins à partir de la valeur définitive de P.

Là avec cette sortie je sais que le "premier bout du chemin" est 4-->3, je sais aussi que le chemin optimal de 3 à 0, c'est 3-->7 et donc on a bien 4,3,7,0

C'est ça, mais tu le ferais faire par un second algorithme.

[Evanou]

Ah mais oui, ce que je veux c'est le prédécesseur de ce que j'ai déjà calculé avant !
Mon code fonctionne, merci beaucoup ! Mais est-ce parce que mon graphe n'est pas pondéré ?
C'est vrai que si je tombe sur une arrête pondérée à 1000000 par exemple il faut tout reprendre depuis le début et tout change... ce qui n'est pas prit en compte dans le code tel qu'il est maintenant si je comprends bien.

A la fin de la boucle, P me donne le dernier nœud pour chaque chemin optimal en provenance de chaque nœud.
Par exemple P= [0, 0, 1, 7 , 3, 3, 7, 0], le chemin optimal pour aller de 3 à 0 (qui est ma source) finit par 7 (puis 0). Je peux recalculer les chemins optimaux pour 7, ce qui donne P = [x,x,x,3,x,x,x,x]. Et encore tous les chemins de 3 à 4 !
Je peux tout récupérer avec cette technique ou c'est trop long et compliqué (et faux?)?

[L.A.]

Effectivement, attention aux algorithmes qui marchent sur des exemples simples, mais plus du tout sur les exemples plus complexes à cause des "vices cachés"...

Ici je pense que ton algo est correct pour P, et ce P te permet de reconstruire tous les chemins minimaux, en partant de la fin jusqu'à la source (P donne l'avant dernier sommet, puis autre entrée de P te donne l'avant-avant dernier, etc.)

[Evanou]

Yes je vais tenter ça en étant méticuleux sur la syntaxe.
Merci beaucoup d'avoir pris sur votre temps pour m'aider, j'ai vraiment l'impression d'y voir plus clair !

[Evanou]

Pour clore le sujet voici mon code final qui a l'air de bien fonctionner !
Merci encore

Code: Tout sélectionner

#edgelist = []

#   for i in range(0,len(mat)):
#       for j in range(0,len(mat)):
 #              if mat[i][j] == 1:
#                   edge = (i,j)
 #                  edgelist.append(edge)

def algo_pcc(src,mat,edgelist):

   L = [math.inf] * len(mat)
   P = [math.inf] * len(mat)
   L[src] = 0
   P[src] = src
   go = True

   while go == True:
       go = False
       for (x,y) in edgelist:
           if L[y] > L[x] + mat[x][y]:
                L[y] = L[x] + mat[x][y]
                P[y] = x
                go = True


   return P,L

## recup les chemin
def recup_chem(mat,src):
   list_path = np.zeros((len(mat),len(mat)))
   n = len(list_path)
   P,L = algo_pcc(src,mat)
   list_path[0] = P
   for i in range(1,n):
       for j in range(0, n):
           if list_path[i-1][j] != src:
               d = int(list_path[i-1][j])
               c = list_path[i-1][d]
               list_path[i][j] = c
   return list_path

[fatal_error]

slt,

pour info tu peux faire plus rapide (encore que pour les metros ca changera rien) avec Djikstra (vu que t'as pas de cycles négatifs).
wiki donne o(E+Vlog(V)) vs O(E*V) de mémoire
wiki donne aussi la procédure de reconstruction du chemin