← Volver a los ejercicios

Dijkstra con pesos negativos

Seis grafos con alguna arista negativa y ningún ciclo negativo. En cada uno se decide qué hace dijkstraST(G, s, t), la versión de uno a uno que se detiene cuando t sale de la cola, y en qué vértice se rompe la propiedad en que descansa el algoritmo: que un vértice que sale de la cola ya tiene su distancia mínima. Después se corren dijkstra y Bellman-Ford sobre el mismo grafo y se comparan.

El grafo

Las aristas negativas van en rojo. La fuente es s y el destino es t.

1. ¿Qué pasa con dijkstraST?

2. ¿En qué vértice se rompe la propiedad?

Es el primer vértice que sale de la cola con una distancia mayor que su distancia mínima, o ninguno si todos salen bien antes de que el algoritmo se detenga.

3. Los dos algoritmos lado a lado

4. Para llevarse

Sin solución aquí. Diga por qué la versión de uno a todos, que acepta una pareja si dist[u] == du y vuelve a meter un vértice cada vez que mejora, termina con las distancias correctas cuando no hay ciclos negativos, y qué pagaría si el grafo fuera grande. Después diga qué ocurriría con dijkstra si hubiera un ciclo negativo alcanzable desde la fuente.