bfm5.cpp es Bellman-Ford con una cola: solo salen
de ella los vértices cuyo d cambió desde la última vez, y el arreglo
enCola evita meter a un vértice que ya está esperando. El arreglo
conteo cuenta cuántas veces entró cada vértice, y si alguno pasa de
n el programa declara un ciclo negativo. Aquí se ejecuta el código
del archivo, línea por línea, sobre tres grafos sin ciclos negativos.
Entrada: n, m y las
m aristas u v peso; la fuente es el vértice 0.
Salida: distancias y predecesores.
Predicción. ¿Cuántas veces sale de la cola cada vértice? Cuente también la salida inicial de la fuente.
bfm5.cpp.
La línea 44 se ejecuta una vez por cada salida de la cola, así que su
contador es el total de salidas. La línea 58, la de conteo, se
ejecuta una vez por cada entrada a la cola (sin contar la inicial).| Vértice | d | p | enCola | conteo | Salidas de la cola |
|---|
Sin solución aquí. En el primer grafo, cambie el
orden en que se leen las aristas del vértice 2 y diga si cambia el número
de salidas de algún vértice. Después diga qué valor tendría conteo
en el vértice más visitado si enCola no existiera, y por qué
la comparación de la línea 61 podría dispararse sin que haya un ciclo
negativo.