Implémentation Python de l’algorithme de floyd-warshall

Introduction – algorithme de floyd warshall python

Implémentation Python de l’algorithme de floyd-warshall

Cet article fait suite à d’autres article sur l’implémentation python d’algorithme : l’article suivant sur l’algorithme de Dijkstra : https://128mots.com/index.php/2020/02/17/lalgorithme-de-dijkstra-dans-un-graphe-pondere-et-oriente-en-plus-de-128-mots/

import numpy as np

def floydwarshall(graph):
    distances = {}
    predecesseurs = {}
    for u in graph:
        distances[u] = {}
        predecesseurs[u] = {}
        for v in graph:
            distances[u][v] = np.inf
            predecesseurs[u][v] = -1
        distances[u][u] = 0
        for voisin in graph[u]:
            distances[u][voisin] = graph[u][voisin]
            predecesseurs[u][voisin] = u

    for t in graph:
        for u in graph:
            for v in graph:
                nouvellesDistances = distances[u][t] + distances[t][v]
                if nouvellesDistances < distances[u][v]:
                    distances[u][v] = nouvellesDistances
                    predecesseurs[u][v] = predecesseurs[t][v] 
    return distances, predecesseurs

#Liste d'ajacence du graphe
graph = {'A':{'B':15,'C':4},'B':{'E':5},'C':{'E':11,'D':2},'D':{'E':3},'E':{}}
distances, predecesseurs = floydwarshall(graph)
print("Prédecesseur du sommet d'arrivée dans le chemin le plus court (-1 : chemin impossible):")
for v in predecesseurs: print(str(v) + '' + str(predecesseurs[v]))
print("Plus courte distance pour chaque sommet de départ (inf : chemin impossible) :")
for v in distances: print(str(v) + '' + str(distances[v]))

Laisser un commentaire

Votre adresse e-mail ne sera pas publiée. Les champs obligatoires sont indiqués avec *