← Volver a los ejercicios

Algoritmo de Dijkstra

Se ejecuta dijkstra, la versión de uno a todos, línea por línea. La cola de prioridad guarda parejas (distancia, vértice) y se muestra ordenada, de modo que la primera pareja es la que sale. Una pareja cuya distancia ya no coincide con dist es vieja y se descarta. El número que acompaña a cada línea es el de su archivo, y el contador dice cuántas veces se ejecuta.

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 extraídos con su distancia final. Ámbar: el vértice u que se procesa. La arista azul es la que se examina, verde si mejora un dist, y las moradas forman el árbol de pred.
Escriba el orden en que los vértices se procesan, separados por espacios (las parejas viejas no cuentan):

2. Ejecute el código

Paso 0 de 0
Cola pqueue
Procesados
Tachada, una pareja vieja: su distancia ya no es la de dist. Cuando sale de la cola se descarta en la línea 45.

3. El estado

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

4. Cuántas parejas entran y cuántas valen

5. Para llevarse

Sin solución aquí. En el primer grafo, cambie el peso de una arista y diga si cambia el orden en que se procesan los vértices. Después diga cuántas parejas habría en la cola si dijkstra metiera todos los vértices al comienzo, como sugiere el comentario de la línea 38, y qué pasaría con las parejas viejas.