Pseudo Code
Lección 4 de 9 del curso Algoritmo de Dijkstra - Algoritmos de grafos 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 es simplemente un número mayor que cualquier distancia real (por ejemplo, 1000000000).
- Elegir el vértice no visitado con la menor distancia en cada ronda es el núcleo voraz (greedy) de Dijkstra. Escanear la lista de aristas plana para relajar mantiene el código simple y funciona en cualquier lenguaje.
Pruébalo tú mismo
Esta lección no incluye un desafío de código.
Ponte a pruebaEsta lección incluye un breve cuestionario. Empieza la lección para responderlo y registrar tu progreso.
Todas las lecciones de Algoritmo de Dijkstra - Algoritmos de grafos
2The Algorithm
How it works?Pseudo CodeImplementation (Part 1)Implementation (Part 2)
Time and Space Complexity