Pseudocodice

Lezione 4 di 9 del corso Algoritmo di Dijkstra - Algoritmi su grafi di 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 è semplicemente un numero più grande di qualsiasi distanza reale (per esempio 1000000000).
Scegliere il vertice non visitato con la distanza minima a ogni iterazione è il cuore dell'algoritmo greedy di Dijkstra. Scorrere l'elenco semplice degli archi per rilassare gli archi mantiene il codice semplice e funziona in qualsiasi linguaggio.

Provalo tu

Questa lezione non include una sfida di codice.