Arborescencia de ruta más corta

Pasos:

1. Iniciacion de etiquetado. Sea d(s)=0 y márquese esta etiqueta como permanente. Sea d(X)= para todo y considérese como etiquetas temporales. Sea a(x)=x. Sea p=s

2. Actualización de etiquetas. Para todo que tenga etiqueta temporal, actualizar las etiquetas de acuerdo a

3. Si d(X) se modificó, hacer a(x)=p. Sea tal que si terminar ya que no hay arborescencia de ruta más corta. En otro caso marcar la etiqueta como permanente sea

   1. Si sólo se desea la ruta de a t, si p=t entonces terminar; d(p) es la longitud del camino más corto si ir al paso 2.

   2. Si se desea la arborescencia, terminar cuando todos los nodos estén marcados de forma permanente. En otro caso, ir al paso 2.

Problema:

La siguiente red proporciona las distancias en millas entre las ciudades 1,2,..3. Encuentra la arborescencia de ruta más corta entre las siguientes ciudades tomando como punto de partida la ciudad 1.

Aplicamos Dijkstra

Obtenemos la siguiente red:

Interpretación:

Aplicando el método de Dijkstra obtenemos la arborescencia de ruta más corta desde un punto origen el cual en este caso es el nodo 1 así para poder observar que ruta es la que nos conviene más para llegar a un punto dado.