Python-Implementierung des Dijkstra-Algorithmus

Dieser Artikel knüpft an den folgenden Artikel zum Dijkstra-Algorithmus an: https://128mots.com/index.php/2020/02/18/implementation-python-de-lalgorithme-de-dijkstra/

Python-Implementierung des Dijkstra-Algorithmus python Dijkstra

Hier ist die Python-Implementierung des Algorithmus





from collections import deque

def dijkstra(graph, vertex):
    queue = deque([vertex])
    distance = {vertex: 0}
    while queue:
        t = queue.popleft()
        print("On visite le sommet " + str(t))
        for voisin in graph[t]:
                queue.append(voisin)
                nouvelle_distance = distance[t] + graph[t][voisin]
                if(voisin not in distance or nouvelle_distance < distance[voisin]):
                    distance[voisin] = nouvelle_distance
                    print("Met à jour le sommet " + str(voisin) + " avec la distance : " + str(nouvelle_distance))
                    
    return distance



#Liste d'ajacence du graphe
graph = {'A':{'B':15,'C':4},'B':{'E':5},'C':{'E':11,'D':2},'D':{'E':3},'E':{}}
distance = dijkstra(graph,'A')
print("Distances" + str(distance))

https://128mots.com/index.php/2019/11/10/filius-simulateur-reseau/

https://128mots.com/index.php/2019/12/03/le-tri-fusion-et-implementation-python-en-moins-de-128-mots/

https://128mots.com/index.php/2019/12/03/le-tri-fusion-et-implementation-python-en-moins-de-128-mots/

https://128mots.com/index.php/2019/12/01/parcours-en-profondeur-dans-les-graphes-et-implementation-python-en-moins-de-128-mots/

https://128mots.com/index.php/2019/12/01/parcours-en-profondeur-dans-les-graphes-et-implementation-python-en-moins-de-128-mots/

https://128mots.com/index.php/2020/04/11/algorithme-le-probleme-du-sac-a-dos-knapsack-problem-en-plus-de-128-mots/

Laisser un commentaire

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