← Volver a los ejercicios

Moore

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.

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.

Grafo:

Sobre cada vértice, d/p. Amarillo: el vértice está en la cola. Contorno grueso: el que acaba de salir. La arista azul se examina y se pone verde si baja un d.

Predicción. ¿Cuántas veces sale de la cola cada vértice? Cuente también la salida inicial de la fuente.

2. Ejecute bfm5.cpp

cola: [ ]
Paso 0 de 0
Salida:

        
El número de cada línea es el de 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).

3. Los arreglos, vértice por vértice

VérticedpenColaconteoSalidas de la cola
La última columna no es una variable del programa: es el recuento de ejecuciones de la línea 44 para ese vértice.

4. Para llevarse

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.