← Volver a los ejercicios

Bellman-Ford

Tres formas de escribir Bellman-Ford en C++: una fila de una matriz por cada ronda (bfm1.cpp), un solo vector que se va actualizando (bfm2.cpp) y la que se detiene cuando una ronda no cambia nada (bfm4.cpp). Aquí se ejecuta el código de cada archivo, línea por línea, sobre tres grafos con pesos negativos y sin ciclos negativos. El número que acompaña a cada línea es el de su archivo, y el contador cuenta las veces que se ejecuta; en una línea for o while son las vueltas.

1. El grafo y la predicción

Entrada: n, m y las m aristas u v peso; la fuente es el vértice 0.  Salida: distancias y predecesores, o el aviso de ciclo negativo.

Grafo:

Sobre cada vértice, d/p, con ∞ para INT_MAX y un guion para p = -1. Las aristas moradas forman el árbol de p; la azul es la que se examina, verde si baja un d y roja si resulta tensa en la revisión final.
¿Cuántas iteraciones realiza bfm4.cpp en este grafo?

2. Ejecute el código

Versión:

Paso 0 de 0
Salida hasta ahora:

        
Las aristas se recorren por vértice de origen, de 0 a n - 1, y dentro de cada vértice en el orden en que se leyeron. En la matriz, d[i] es el estado tras la ronda i.

3. El estado

4. Lo que examina cada versión

5. Para llevarse

Sin solución aquí. En el segundo grafo, cambie el orden en que se leen las aristas y diga si bfm4.cpp sigue haciendo las mismas iteraciones. Después diga cuántas iteraciones haría en un camino de n vértices cuyas aristas se leen en el mismo sentido en que se recorre, y cuántas en el sentido contrario.