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.
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.
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.bfm4.cpp en este grafo?
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.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.