Implémentation Python de l’algorithme de Bellman-Ford

Introduction – algorithme de Bellman-Ford python

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/2021/03/01/implementation-python-de-lalgorithme-de-floyd-warshall/

def bellmanFord(graph, sommetDepart):
    distances = {} 
    predecesseurs = {}
    for sommet in graph:
        distances[sommet] = np.inf
        predecesseurs[sommet] = None
    distances[sommetDepart] = 0
    

    for i in range(len(graph)-1):
        for j in graph:
            for k in graph[j]: 
                if distances[k] > distances[j] + graph[j][k]:
                    distances[k]  = distances[j] + graph[j][k]
                    predecesseurs[k] = j
    for i in graph:
        for j in graph[i]:
            assert distances[j] <= distances[i] + graph[i][j]

    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 = bellmanFord(graph,'A')
print("Plus courte distance pour chaque sommet de départ :")
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 *