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.
dijkstraST?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.
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.