Ejercicios resueltos de caminos mínimos

• Distancias: $d[S] = 0$, $d[v] = \infty$ para $v \neq S$
• Conjunto visitados: $V_{visited} = \emptyset$
• Predecesores: $pred[v] = null$ para todo $v$

Iteración 1 (seleccionar S):

• Relajar $(S,A)$: $d[A] = \min(\infty, 0 + 4) = 4$, $pred[A] = S$
• Relajar $(S,B)$: $d[B] = \min(\infty, 0 + 2) = 2$, $pred[B] = S$

Iteración 2 (seleccionar B):

• Relajar $(B,A)$: $d[A] = \min(4, 2 + 1) = 3$, $pred[A] = B$
• Relajar $(B,D)$: $d[D] = \min(\infty, 2 + 5) = 7$, $pred[D] = B$

Iteración 3 (seleccionar A):

• Relajar $(A,C)$: $d[C] = \min(\infty, 3 + 3) = 6$, $pred[C] = A$
• Relajar $(A,D)$: $d[D] = \min(7, 3 + 6) = 7$ (no mejora)

Iteración 4 (seleccionar C):

• Relajar $(C,T)$: $d[T] = \min(\infty, 6 + 2) = 8$, $pred[T] = C$

Iteración 5 (seleccionar D):

• Relajar $(D,C)$: $d[C] = \min(6, 7 + 1) = 6$ (no mejora)
• Relajar $(D,T)$: $d[T] = \min(8, 7 + 4) = 8$ (no mejora)

Desde S a cada vértice:

• S → A: S → B → A, distancia = 3
• S → B: S → B, distancia = 2
• S → C: S → B → A → C, distancia = 6
• S → D: S → B → D, distancia = 7
• S → T: S → B → A → C → T, distancia = 8

Usar el grafo dirigido con vértices {1, 2, 3, 4} y aristas:

$(1{,}2{,}3)$, $(1{,}4{,}7)$, $(2{,}3{,}1)$, $(2{,}4{,}2)$, $(3{,}4{,}6)$, $(4{,}1{,}2)$, $(4{,}3{,}4)$

Matriz de distancias inicial:

$$D^{(0)} = \begin{pmatrix} 0 & 3 & \infty & 7 \\ \infty & 0 & 1 & 2 \\ \infty & \infty & 0 & 6 \\ 2 & \infty & 4 & 0 \end{pmatrix}$$

Iteración k=1 (via vértice 1):

$$D^{(1)} = \begin{pmatrix} 0 & 3 & \infty & 7 \\ \infty & 0 & 1 & 2 \\ \infty & \infty & 0 & 6 \\ 2 & 5 & 4 & 0 \end{pmatrix}$$

Iteración k=2 (via vértice 2):

$$D^{(2)} = \begin{pmatrix} 0 & 3 & 4 & 5 \\ \infty & 0 & 1 & 2 \\ \infty & \infty & 0 & 6 \\ 2 & 5 & 4 & 0 \end{pmatrix}$$

Iteración k=3 (via vértice 3):

$$D^{(3)} = \begin{pmatrix} 0 & 3 & 4 & 5 \\ \infty & 0 & 1 & 2 \\ \infty & \infty & 0 & 6 \\ 2 & 5 & 4 & 0 \end{pmatrix}$$

Iteración k=4 (via vértice 4):

$$D^{(4)} = \begin{pmatrix} 0 & 3 & 4 & 5 \\ 4 & 0 & 1 & 2 \\ 8 & 11 & 0 & 6 \\ 2 & 5 & 4 & 0 \end{pmatrix}$$

Desde vértice 1: d(1)=0, d(2)=3, d(3)=4, d(4)=5

Desde vértice 2: d(1)=4, d(2)=0, d(3)=1, d(4)=2

Desde vértice 3: d(1)=8, d(2)=11, d(3)=0, d(4)=6

Desde vértice 4: d(1)=2, d(2)=5, d(3)=4, d(4)=0

Ambos algoritmos producen la misma matriz de distancias mínimas:

$$\text{Distancias} = \begin{pmatrix} 0 & 3 & 4 & 5 \\ 4 & 0 & 1 & 2 \\ 8 & 11 & 0 & 6 \\ 2 & 5 & 4 & 0 \end{pmatrix}$$

Floyd-Warshall:

• Complejidad temporal: $O(n^3)$
• Complejidad espacial: $O(n^2)$
• Calcula todos los pares de caminos mínimos

Dijkstra (desde todos los vértices):

• Complejidad temporal: $O(n \cdot (n + m) \log n)$ con heap binario
• Para grafos densos ($m = O(n^2)$): $O(n^3 \log n)$
• Complejidad espacial: $O(n)$ por ejecución

Usar Floyd-Warshall cuando:

• Necesitas distancias entre todos los pares de vértices
• El grafo es denso ($m \approx n^2$)
• El grafo es pequeño ($n \leq 400$)
• Pueden existir aristas con pesos negativos (pero sin ciclos negativos)

Usar Dijkstra cuando:

• Solo necesitas caminos desde una fuente específica
• El grafo es disperso ($m \ll n^2$)
• El grafo es grande ($n > 1000$)
• Todos los pesos son no negativos
• Necesitas reconstruir los caminos completos, no solo las distancias

Caso híbrido:

Para $k < n$ fuentes específicas: ejecutar Dijkstra $k$ veces puede ser más eficiente que Floyd-Warshall si $k \ll n$.

Estrategia: Usar una variación del algoritmo de Dijkstra que mantiene los dos mejores caminos a cada vértice.

Modificaciones:

• Mantener dos distancias por vértice: $d_1[v]$ (mínima) y $d_2[v]$ (segunda mínima)
• Usar un heap que puede contener hasta 2 entradas por vértice
• Procesar cada vértice hasta 2 veces

Grafo de ejemplo: Del ejercicio anterior, desde vértice 1.

Inicialización:

• $d_1[1] = 0$, $d_2[1] = \infty$
• $d_1[v] = d_2[v] = \infty$ para $v \neq 1$

Desde vértice 1:

• Vértice 2: 1º camino = 3, 2º camino = 10
• Vértice 3: 1º camino = 4, 2º camino = 9
• Vértice 4: 1º camino = 5, 2º camino = 7

Para reconstruir caminos, mantener predecesores para ambas distancias:

Segundos caminos desde vértice 1:

• 1 → 2: La única arista que llega a 2 es (1,2), así que no hay un segundo camino simple
• Segundo recorrido (con ciclo): 1 → 2 → 4 → 1 → 2 = 3 + 2 + 2 + 3 = 10
• 1 → 3: 1 → 2 → 4 → 3, peso = 3 + 2 + 4 = 9
• 1 → 4: 1 → 2 → 4 → 1 → 4, pero esto contiene ciclo
• Segundo camino válido: 1 → 4 (directo), peso = 7

Todos los caminos de 1 a 4:

1. Directo: 1 → 4, peso = 7
2. Via 2: 1 → 2 → 4, peso = 3 + 2 = 5 $\checkmark$ (mínimo)
3. Via 2, luego ciclo: 1 → 2 → 4 → 1 → 4, peso = 5 + 2 + 7 = 14

Resultado correcto: 1º camino = 5, 2º camino = 7

• Temporal: $O((n + m) \log n)$ (igual que Dijkstra estándar)
• Espacial: $O(n)$ para almacenar las dos distancias por vértice
• Cada vértice se procesa a lo sumo 2 veces

Principio: Si no hay ciclos negativos, las distancias mínimas se estabilizan en a lo sumo $n-1$ iteraciones.

Detección de ciclos negativos: Si después de $n-1$ iteraciones, alguna distancia puede seguir mejorando, existe un ciclo negativo.

Bellman-Ford-Detect-Negative-Cycle(G, s):

1. Inicializar d[s] = 0, d[v] = $\infty$ para v ≠ s
2. Para i = 1 hasta n-1:

Para cada arista (u,v) con peso w:

Si d[u] + w < d[v]:

d[v] = d[u] + w

3. Para cada arista (u,v) con peso w:

Si d[u] + w < d[v]:

RETURN "Ciclo negativo detectado"

4. RETURN "No hay ciclos negativos"

Vértices: {A, B, C, D}

Aristas dirigidas con pesos:

• $(A,B,1)$
• $(B,C,-3)$
• $(C,D,2)$
• $(D,B,-2)$ ← Esta arista crea el ciclo negativo
• $(A,D,5)$

Ciclo negativo: B → C → D → B con peso total: $-3 + 2 + (-2) = -3$

Inicialización: $d[A] = 0$, $d[B] = d[C] = d[D] = \infty$

Iteración 1:

• Relajar $(A,B)$: $d[B] = \min(\infty, 0+1) = 1$
• Relajar $(A,D)$: $d[D] = \min(\infty, 0+5) = 5$
• Estado: $d[A]=0, d[B]=1, d[C]=\infty, d[D]=5$

Iteración 2:

• Relajar $(B,C)$: $d[C] = \min(\infty, 1+(-3)) = -2$
• Relajar $(C,D)$: $d[D] = \min(5, -2+2) = 0$
• Estado: $d[A]=0, d[B]=1, d[C]=-2, d[D]=0$

Iteración 3 (n-1 = 3 para 4 vértices):

• Relajar $(D,B)$: $d[B] = \min(1, 0+(-2)) = -2$
• Relajar $(B,C)$: $d[C] = \min(-2, -2+(-3)) = -5$
• Relajar $(C,D)$: $d[D] = \min(0, -5+2) = -3$
• Estado: $d[A]=0, d[B]=-2, d[C]=-5, d[D]=-3$

Iteración 4 (verificación):

• Relajar $(D,B)$: $d[B] = \min(-2, -3+(-2)) = -5$ $\checkmark$ Mejora detectada
• Relajar $(B,C)$: $d[C] = \min(-5, -5+(-3)) = -8$ $\checkmark$ Mejora detectada

Conclusión: Se detectó un ciclo negativo porque las distancias siguieron mejorando.

Algoritmo extendido: Después de detectar el ciclo, marcar todos los vértices alcanzables desde los vértices que siguen mejorando.

Marcar-Vertices-Ciclo-Negativo():

1. Ejecutar n-1 iteraciones normales
2. En la iteración de verificación:
   • Marcar vértices cuyas distancias mejoran
3. Hacer BFS/DFS desde vértices marcados
   • Marcar todos los alcanzables

Vértices afectados: B, C, D (todos están en el ciclo o son alcanzables desde él)

Vértices no afectados: A (no está en camino hacia el ciclo negativo)

Detección de arbitraje en sistemas financieros:

• Vértices = monedas
• Aristas = tasas de cambio (logaritmos negativos)
• Ciclo negativo = oportunidad de arbitraje

Detección de inconsistencias en sistemas de restricciones:

• Vértices = variables
• Aristas = restricciones de diferencia
• Ciclo negativo = sistema inconsistente