← Volver a los ejercicios

Ciclo negativo

Con un ciclo negativo alcanzable las distancias no existen, y los dos programas lo notan de maneras distintas. bfm3.cpp hace n rondas completas y, si la última todavía cambió algo, sube por los predecesores hasta caer dentro del ciclo y lo guarda. bfm5.cpp usa la cola y se rinde cuando conteo de un vértice pasa de n. Aquí se ejecutan los dos sobre tres grafos con ciclos negativos, en el código exacto de cada archivo.

1. El grafo y la predicción

Grafo:

Sobre cada vértice, d/p. Las aristas moradas forman el árbol de p; la azul es la que se examina y la verde la que baja un d. Los vértices con contorno rojo son los del ciclo, cuando ya se recuperó.

Predicción. bfm3.cpp imprime los vértices de un ciclo negativo. Marque cuáles son.

2. Ejecute el código

Versión:

ciclo: [ ]
Paso 0 de 0
Salida hasta ahora:

        
En bfm3.cpp el ciclo se lee al revés: cada elemento es el predecesor del anterior. Las líneas con aqui son impresiones del archivo.

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

4. Para llevarse

Sin solución aquí. En el tercer grafo, diga qué vértice es t al terminar las rondas de bfm3.cpp y por qué subir n veces por p desde él cae en uno de los dos ciclos y no en el otro. Después cambie el peso de la arista 2 → 1 a 3 y diga qué imprime el programa.