[PYTHON] Reconstruction du chemin trouvé par l'algorithme de Floyd-Warshall

Le problème exposé dans ce sujet a été résolu.

Bonjour,

Je poste ce message car je suis confronté à un problème : j’ai implémenté en Python l’algorithme de Floyd-Warshall en Python comme suit :

def FloydWarshall(G, n): 
    """Cette fonction trouve le plus court chemin d'un Ge G entre un sommet de départ et un sommet d'arrivee (la destination) à l'aide de l'algorithme de Floyd-Warshall.
    G est la matrice d'adjacence du graphe et n la taille de celle-ci (une matrice d'adjacence est une matrice carrée de taille n*n)"""

    graphe = G.copy() # On copie la liste de départ pour éviter de réecrire par-dessus

    # On applique directement la formule de l'algorithme
    for k in range(n):
        for i in range(n):
            for j in range(n): 
                graphe[i][j] = min(graphe[i][j], graphe[i][k] + graphe[k][j])
                
    return graphe # Renvoie une matrice du coût de chaque trajet

Cette fonction marche parfaitement en renvoyant la matrice des distances entre chaque sommet mais j’aimerai maintenant modifier cette fonction afin qu’elle puisse aussi renvoyer le chemin le plus court entre chaque sommets, mais je ne vois pas trop comment faire… Serait-il possible de me donner des pistes ?

Je vous remercie par avance pour votre réponse !

+0 -0

Salut !

Déjà merci pour ta réponse ! J’ai essayé de faire ça :


def FloydWarshallAvecReconstruction(matrice, n):

    distances, suivants = [[0 for _ in range(n)] for _ in range(n)], [[0 for _ in range(n)] for _ in range(n)]

    for i in range(n):
        for j in range(n):
            distances[i][j] = matrice[i][j]
            suivants[i][j] = j

    for i in range(n):
        distances[i][i] = 0
        suivants[i][i] = i

    for k in range(1, n):
        for i in range(1, n):
            for j in range(1, n):
                if distances[i][j] > distances[i][k] + distances[k][j]:
                    distances[i][j] = distances[i][k] + distances[k][j]
                    suivants[i][j] = suivants[i][k]  

    return suivants

def FloydWarshallChemin(sommets, depart, arrivee):

    if sommets[depart][arrivee] == 0:
        return []

    chemin = [depart]

    while depart != arrivee:
        depart = sommets[depart][arrivee]
        chemin.append(depart)
        
    return chemin

Mais le chemin que j’obtiens est juste la liste [depart, arrivee] (avec le depart et l’arrivee qui sont les mêmes que les arguments de la fonction). Si j’essaye d’afficher la liste suivants j’obtiens [0, 1, 2, 3, 4, 5] ce qui correspond juste à la liste de sommets (j’ai 6 sommets) mais je ne vois pas trop ou je me suis trompé …

+0 -0

Je vois plusieurs problèmes:

  • ta fonction FloydWarshallChemin n’appelle pas FloydWarshallAvecReconstruction
  • dans la boucle while depart != arrivee (au passage je trouve très maladroit de modifier une variable qui est un paramètre de la fonction, tu devrais définir une variable intérmediaire pos = depart et ensuite while pos != arrivee) tu n’utilises pas le tableau suivants calculé par la première fonction, donc ça ne peut pas marcher.

suivants[i][j] indique à quel sommet aller, depuis i, pour suivre le plus court chemin entre i et j.

+0 -0

(au passage je trouve très maladroit de modifier une variable qui est un paramètre de la fonction, tu devrais définir une variable intérmediaire pos = depart et ensuite while pos != arrivee)

C’est vrai ! J’ai rajouté une variable intermédiaire. En fait, j’appelle la fonction comme ça :

    print("\nFloyd–Warshall, affichage du chemin : ")
    test = FloydWarshallAvecReconstruction(matG, n)
    print(FloydWarshallChemin(test, 0, 4))

Donc le paramètre sommets dans FloydWarshallChemin correspond en fait à la liste renvoyée par FloydWarshallAvecReconstruction, donc j’utilise bien suivants dans la boucle while. Du coup je ne vois pas ce qui bloque :(.

+0 -0

Je ne trouve pas très clair d’appeler sommets le tableau qui avant s’appelait suivants, à la rigueur prochain_sommet m’aurait permis de comprendre.

Ton code m’a l’air de retranscrire assez fidèlement ce qui est dans Wikipédia. Est-ce que tu es sûr que le résultat est incorrect ? Ça aiderait de montrer le graphe en entrée, le tableau suivants calculé, tes choix de depart, arrivee et le résultat ?

(Dans ton message tu dis que suivants est calculé comme [0,1,2,3,4,5], mais c’est bizarre puisque c’est un tableau à deux dimensions.)

+0 -0

C’est vrai que mon message manquait un peu de rigueur, voici un peu plus de détail :

  • Le tableau suivants renvoyé avec mon graphe de 6 sommets est plus exactement : [[0, 1, 2, 3, 4, 5], [0, 1, 2, 3, 4, 5], [0, 1, 2, 3, 4, 5], [0, 1, 2, 3, 4, 5], [0, 1, 2, 3, 4, 5], [0, 1, 2, 3, 4, 5]] (une liste 6*6 donc)

  • Le résultat renvoyé par FloydWarshallChemin avec :

    print("\nFloyd–Warshall, affichage du chemin : ")
    test = FloydWarshallAvecReconstruction(matG, n)
    print(FloydWarshallChemin(test, 0, 4))

est [0, 4]; [0, 5] si je fais FloydWarshallChemin(test, 0, 5) par exemple.

  • Le résultat est bien incorrect, il devrait renvoyer A -> C -> E (donc 0, 2, 4) pour un coût de 3.

  • Je représente mon graphe avec un dictionnaire :

    graphe = { # Graphe Arbitraire

        'A': {'B': 2, 'C': 1},
        'B': {'A': 2, 'C': 4, 'D': 8},
        'C': {'A': 1, 'B': 4, 'E': 2},
        'D': {'B': 8, 'E': 11, 'F': 4},
        'E': {'C': 2, 'D': 11, 'F': 5},
        'F': {'D': 4, 'E': 5}

    }

et je trouve sa matrice d’adjacence avec :

def trouver_matrice_adjacente(G):
    """Fonction prenant en paramètre un graphe sous forme de dictionnaire et renvoie sa matrice d'adjacence et sa taille"""

    liste_sommets = list(G)
    n = len(G) # Taille de la matrice d'adjacence
    matrice = [[0 for _ in range(n)] for _ in range(n)] # Matrice finale vide
    i, j = 0, 0 # Index et compteur
    
    # On remplace dans la matrice, au bon index, les 0 par les distances entre le sommet et ses voisins
    for sommet in G:
        for voisin in G[sommet]:
            i = liste_sommets.index(voisin)
            matrice[i][j] = G[sommet][voisin]
        j += 1 
    
    # On remplace tout les éléments qui ne sont pas des distances et qui ne sont pas sur la diagonale par des INF (sinon il y a un problème avec le min dans la fonction FloydWarshall)
    for i in range(n):
        for j in range(n):
            if i != j and matrice[i][j] == 0:
                matrice[i][j] = float("inf")

    return (matrice, n) # Renvoie la matrice et sa taille

J’utilise aussi la matrice d’adjacence trouvée avec la fonction FloydWarshall sans le chemin de mon premier post et la matrice des distances renvoyée est correcte.

+0 -0

Le bug est vicieux: c’est ton G.copy() du début qui fait tout foirer. (Regarde la valeur de ta matrice avant et après ton appel à FloydWarshall, tu verras.)

Ça marche avec la version bête:

    graphe = [[G[i][j] for j in range(n)] for i in range(n)]

(Donc le bug n’était pas dans le nouveau code mais dans l’ancien.)

+1 -0

Effectivement, le bug était caché merci ! Comme quoi ça sert d’envoyer tout le code dès le début :p La liste de sommets est maintenant : [[0, 1, 2, 3, 4, 5], [0, 1, 2, 3, 2, 2], [0, 1, 2, 4, 4, 4], [0, 1, 5, 3, 5, 5], [0, 2, 2, 5, 4, 5], [0, 4, 4, 3, 4, 5]] ce qui me semble un peu mieux, mais FloydWarshallChemin renvoie toujours [0, 4] (le chemin [depart, arrivee]) avec ce code :

def FloydWarshallChemin(prochain_sommets, depart, arrivee):

    position = depart 

    if prochain_sommets[depart][arrivee] == 0:
        return []

    chemin = [depart]

    while position != arrivee:
        position = prochain_sommets[position][arrivee]
        chemin.append(position)
        
    return chemin
+0 -0

Salut,

Une note rapide sur cette histoire de copie, tu peux regarder du côté de copy.deepcopy qui fait essentiellement la même chose que les listes imbriquées à la main proposées plus haut mais rend l’intention de ton code explicite (et fonctionnerait avec plus de dimensions ou des conteneurs différents).

+3 -0

Merci adri1 pour ton conseil ! J’ai retesté qu’avec ce code :


def trouver_matrice_adjacente(G):
    """Fonction prenant en paramètre un graphe sous forme de dictionnaire et renvoie sa matrice d'adjacence et sa taille"""

    liste_sommets = list(G)
    n = len(G) # Taille de la matrice d'adjacence = n*n
    matrice = [[0 for _ in range(n)] for _ in range(n)] # Matrice finale vide
    i, j = 0, 0 # Index et compteur
    
    # On remplace dans la matrice, au bon index, les 0 par les distances entre le sommet et ses voisins
    for sommet in G:
        for voisin in G[sommet]:
            i = liste_sommets.index(voisin)
            matrice[i][j] = G[sommet][voisin]
        j += 1 
    
    # On remplace tout les éléments qui ne sont pas des distances et qui ne sont pas sur la diagonale par des INF (sinon il y a un problème avec le min dans la fonction FloydWarshall)
    for i in range(n):
        for j in range(n):
            if i != j and matrice[i][j] == 0:
                matrice[i][j] = float("inf")

    return (matrice, n) # Renvoie la matrice et sa taille

def FloydWarshallAvecReconstruction(matrice, n):

    distances, suivants = [[0 for _ in range(n)] for _ in range(n)], [[0 for _ in range(n)] for _ in range(n)]

    for i in range(n):
        for j in range(n):
            distances[i][j] = matrice[i][j]
            suivants[i][j] = j

    for i in range(n):
        distances[i][i] = 0
        suivants[i][i] = i

    for k in range(1, n):
        for i in range(1, n):
            for j in range(1, n):
                if distances[i][j] > distances[i][k] + distances[k][j]:
                    distances[i][j] = distances[i][k] + distances[k][j]
                    suivants[i][j] = suivants[i][k]  

    return suivants

def FloydWarshallChemin(prochain_sommets, depart, arrivee):

    if prochain_sommets[depart][arrivee] == 0:
        return []

    chemin = [depart]
    
    position = depart 

    while position != arrivee:
        position = prochain_sommets[position][arrivee]
        chemin.append(position)
        
    return chemin

if __name__ == "__main__":

    # On utilise un dictionnaire pour décrire le graphe, de type : { 'nom_du_sommet': {nom_sommetVoisin1: poids_trajet1, nom_sommetVoisin2: poids_trajet2} }.

    graphe = { # Graphe Arbitraire

        'A': {'B': 2, 'C': 1},
        'B': {'A': 2, 'C': 4, 'D': 8},
        'C': {'A': 1, 'B': 4, 'E': 2},
        'D': {'B': 8, 'E': 11, 'F': 4},
        'E': {'C': 2, 'D': 11, 'F': 5},
        'F': {'D': 4, 'E': 5}

    }

    matG, n = trouver_matrice_adjacente(graphe)
    test = FloydWarshallAvecReconstruction(matG, n)

    print(FloydWarshallChemin(test, 0, 4))

Et il me renvoie toujours [0, 4]…

+0 -0

Ah, ce sont tes range(1,n) qui sont foireux, il faut utiliser range(n) ou alors range(0,n).

Au passage: pas besoin de trimballer la taille de ta matrice sur le côté, tu peux la récupérer facilement avec len(mat) (len(mat[0]) pour la deuxième dimension, mais ici elles sont carrées donc pas besoin). Ça évite les erreurs où le paramètre passé est le mauvais.

+1 -0
Connectez-vous pour pouvoir poster un message.
Connexion

Pas encore membre ?

Créez un compte en une minute pour profiter pleinement de toutes les fonctionnalités de Zeste de Savoir. Ici, tout est gratuit et sans publicité.
Créer un compte