Dijkstra

Problema: Encontrar la distancia mínima para llegar de un nodo s, a otro nodo t del grafo.

Ejemplo:

1. Para el siguiente grafo:

   

Entrada: s=1, t=4. Salida: 30

Idea del algoritmo:

En cada iteración se añade un vértice al árbol de vértices para los que ya se conoce el camino más corto de s. Se registran los mejores caminos vistos hasta el momento para todos los vértices fuera del árbol y se va insertando en orden de costo creciente.

¿Cómo se evalúa la prioridad de los vértices aún no explorados? El vértice ajeno al árbol que queremos añadir al camino más corto, depende simultáneamente del peso del nuevo arco y de la distancia desde el nodo inicial hasta el nodo del árbol a cual es adyacente.

Código

Disponible en Enciclopedia Algoritmos C++

Complejidad: O(V.E)

Donde V es la cantidad de vértices y E la cantidad de arcos del grafo.

Problemas en sitios jueces que se pueden resolver con Dijkstra

• [UVA online judge – “Sending email”]

  (https://onlinejudge.org/external/109/10986.pdf)

• [URI online judge – “Route Change”]

  (https://www.urionlinejudge.com.br/judge/es/problems/view/1123)

Colaborador autor del artículo:

Emilio Musso.

Fecha ultima modificación:

26 de Noviembre de 2019.