Algoritmo de Dijkstra
Complejidad: O(m + n log n)
Grafo:
Paso 1 / 0
Velocidad:500ms
Pseudocódigo Dijkstra
1function Dijkstra(G, source):
2 for each vertex v in G:
3 dist[v] ← ∞
4 prev[v] ← null
5 dist[source] ← 0
6 Q ← priority queue with all vertices
7
8 while Q is not empty:
9 u ← vertex in Q with min dist[u]
10 remove u from Q
11
12 for each neighbor v of u:
13 alt ← dist[u] + weight(u, v)
14 if alt < dist[v]:
15 dist[v] ← alt
16 prev[v] ← u
17 decrease-key(Q, v, alt)
18
19 return dist, prev
Ejecuta el algoritmo para ver el estado
Leyenda de Colores
No visitado
En cola (frontier)
Procesando
Completado
Arista relajando
Camino más corto
¿Cómo funciona Dijkstra?
- Inicialización: Asigna distancia 0 al nodo fuente y ∞ a todos los demás. Agrega todos los nodos a una cola de prioridad.
- Extracción: En cada iteración, extrae el nodo con la menor distancia de la cola. Este nodo está "completo" - su distancia final ha sido encontrada.
- Relajación: Para cada vecino del nodo actual, calcula si pasar por el nodo actual ofrece un camino más corto. Si es así, actualiza la distancia.
- Repetir: Continúa hasta que la cola esté vacía o todos los nodos alcanzables hayan sido procesados.
Bottleneck del Sorting
El algoritmo mantiene un ordenamiento implícito de los vértices por distancia. Esto requiere Ω(n log n) operaciones de comparación, lo cual se creía era el límite inferior para SSSP. El nuevo algoritmo BMSSP rompe esta barrera.