Pseudo Code
Leçon 4 sur 9 du cours Algorithme de Dijkstra - Algorithmes de graphes de Coddy.
dijkstra(n, edges, source):
dist = [INF, INF, ...]; dist[source] = 0
visited = all false
repeat n times:
u = unvisited vertex with smallest dist (none reachable -> stop)
visited[u] = true
for each edge (a -> b, weight w):
if a == u and dist[u] + w < dist[b]:
dist[b] = dist[u] + w
replace every remaining INF with -1
return dist- INF est simplement un nombre plus grand que n'importe quelle distance réelle (par exemple 1000000000).
- Choisir le sommet non visité avec la plus petite distance à chaque tour est le cœur glouton de Dijkstra. Parcourir la liste d'arêtes plate pour la relaxation maintient le code simple et fonctionne dans tous les langages.
Essayez vous-même
Cette leçon ne comprend pas de défi de code.
Testez-vousCette leçon comprend un petit quiz. Commencez la leçon pour y répondre et suivre votre progression.
Toutes les leçons de Algorithme de Dijkstra - Algorithmes de graphes
2The Algorithm
How it works?Pseudo CodeImplementation (Part 1)Implementation (Part 2)
Time and Space Complexity