Pseudokod

Lekcja 4 z 9 w kursie Algorytm Dijkstry — algorytmy grafowe w 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 to po prostu liczba większa niż każda rzeczywista odległość (na przykład 1000000000).
Wybieranie w każdej rundzie nieodwiedzonego wierzchołka o najmniejszej wartości dist to zachłanne sedno algorytmu Dijkstry. Przeglądanie płaskiej listy krawędzi podczas relaksacji upraszcza kod i działa w każdym języku.

Spróbuj swoich sił

Ta lekcja nie zawiera wyzwania z kodem.