Shortest Path Algorithms resuelven el problema de encontrar la ruta de mínimo costo entre nodos en un grafo ponderado. Tres algoritmos principales cubren distintos casos:

• “Dijkstra: pesos no-negativos, single-source.
• Bellman-Ford: pesos negativos permitidos, detecta ciclos negativos.
• Floyd-Warshall: todos los pares de nodos, O(V³).

Cómo Funcionan

Dijkstra

Mantén un min-heap de (distancia, nodo). Relaja aristas desde el nodo con menor distancia no procesada. Garantiza optimalidad porque siempre extrae el nodo con distancia mínima confirmada.

Bellman-Ford

Relaja todas las aristas V-1 veces. Cada pasada garantiza que las distancias más cortas usan hasta i aristas. Detecta ciclos negativos en la pasada V.

Floyd-Warshall

DP: dp[i][j][k] = shortest path de i a j usando solo vértices 0..k como intermedios. Optimiza a 2D: dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j]).

Idea Clave

Dijkstra es greedy: cada paso elige el nodo más prometedor (menor distancia conocida) y lo confirma. Eso funciona solo sin pesos negativos.

Bellman-Ford es DP: relaja todas las aristas repetidamente, propagando mejoras de distancia. V-1 pasadas bastan porque shortest path tiene a lo sumo V-1 aristas.

Floyd-Warshall es DP sobre intermediarios: construye soluciones permitiendo cada vértice como paso intermedio.

Ejemplo Trabajado

Grafo con pesos:

0→1 (4), 0→2 (1)
1→3 (1)
2→1 (2), 2→3 (5)
3→4 (3)

Fuente: 0.

Dijkstra:

• Inicia: dist[0]=0, heap=[(0,0)].
• Extrae (0,0): relaja 0→1 (4), 0→2 (1). Heap: [(1,2), (4,1)].
• Extrae (1,2): relaja 2→1 (1+2=3 < 4), 2→3 (1+5=6). Heap: [(3,1), (4,1), (6,3)].
• Extrae (3,1): relaja 1→3 (3+1=4 < 6). Heap: [(4,1), (4,3), (6,3)].
• Extrae (4,1): ya procesado, skip.
• Extrae (4,3): relaja 3→4 (4+3=7). Heap: [(6,3), (7,4)].
• Extrae (6,3): ya procesado.
• Extrae (7,4): fin.

Distancias finales: [0, 3, 1, 4, 7].

Casos Extremos y Trampas

• Pesos negativos — Dijkstra falla; usa Bellman-Ford.
• Ciclo negativo — Bellman-Ford lo detecta en la pasada V.
• Grafo disperso — Dijkstra con heap es O((V+E) log V).
• Grafo denso — Floyd-Warshall O(V³) puede ser aceptable para V ≤ 500.
• Single-source — Dijkstra y Bellman-Ford; all-pairs — Floyd-Warshall.

Comparación

Aplicaciones

• Redes de computadoras — routing tables (Dijkstra en OSPF)
• Mapas y navegación — Google Maps, Waze
• Finanzas — detección de arbitraje (ciclos negativos)
• Juegos — pathfinding (A* = Dijkstra + heurística)

Trayectoria de Práctica

1. Implementa Dijkstra con min-heap; traza el ejemplo.
2. Implementa Bellman-Ford; detecta ciclo negativo en un grafo de prueba.
3. Implementa Floyd-Warshall para V=4.
4. ¿Por qué Dijkstra falla con pesos negativos? Da un contraejemplo.
5. Investiga A*: ¿cómo modifica Dijkstra con una heurística?

”