← Volver a los ejercicios

Caminos más cortos en un DAG

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.

1. El grafo y la predicción

Grafo:

Sobre cada vértice, dist/pred, con ∞ para 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.

2. Ejecute el código

Paso 0 de 0
Cola q
Orden topo
El orden de la cola sale de revisar los vértices de 0 a n - 1 y de recorrer las aristas de cada vértice en el orden en que están en G[u].

3. El estado

En ámbar, el vértice que se procesa. En verde, el valor que acaba de bajar.

4. Lo que relaja cada algoritmo

5. Para llevarse

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.