Se ejecuta ssspDAG línea por línea, con el topoSort
de Kahn que lo precede. Primero se calcula el orden topológico y después una sola pasada relaja
las aristas de cada vértice en ese orden. El número que acompaña a cada línea es el de su
archivo, y el contador dice cuántas veces se ejecuta; en una línea for o
while son las vueltas.
INF y un guion para -1.
Verde claro: vértices ya procesados. Ámbar: el vértice u que se procesa. La arista azul es la que se examina,
verde si baja una distancia, y las moradas forman el árbol de pred.qtopon - 1
y de recorrer las aristas de cada vértice en el orden en que están en G[u].Sin solución aquí. En el primer grafo, cambie el orden en que están
escritas las aristas de un vértice y diga si cambia el orden topológico que sale de
topoSort y si cambia dist. Después diga qué pasaría con
ssspDAG si se le entrega un grafo con un ciclo.