Para un pico de origen dado en el gráfico, el algoritmo busca la ruta más corta entre ese nodo y todos los demás.
Aquí se utiliza un gráfico ponderado, que es un gráfico en el que cada arco (caso de un gráfico orientado) recibe un peso. Por lo tanto, un gráfico ponderado es un tipo especial de gráfico etiquetado en el que las etiquetas son números.
El peso de una cadena o trayectoria es la suma de los pesos de los arcos que componen la cadena.
El algoritmo entra en un gráfico ponderado y una cumbre a partir de la cual calcula las distancias, los pasos son:
Fase de inicialización:
- En todas las partes superiores, una etiqueta igual al infinito (o en la longitud máxima posible – 1) se coloca en todas las partes superiores.
- La etiqueta se inicia en A a 0
Fase de tratamiento:
- Tratamos una cumbre (aquí comenzamos con A)
- Marcamos la cumbre como visitada
- Liberamos los arcos salientes de la cumbre, es decir, tratamos de actualizar el valor de la etiqueta de la parte superior del acabado por distancia.
- Si el valor de la carretera hasta la parte superior del acabado es inferior al calculado, la etiqueta superior se actualiza con esta distancia total.
- La siguiente parte superior a tratar es la que tiene el peso más bajo.
Ejemplo:
libera el arco de salida C-E, la distancia calculada desde la parte superior A es 4 – 11 – 15. 15 siendo mejor que el infinito actualizamos la etiqueta de la parte superior E.
On libera el arco saliente D-E y calcula la distancia desde la parte superior A que es igual a 9 o una distancia inferior a 15 (calculado en la etapa anterior)A con
tinuación, anulamos la selección del arco C-E que anteriormente se calculó como la mejor ruta para ir de la A a la E y se actualiza la cumbre E con el valor
9.La cumbre E se sigue tratada, no hay arco saliente por lo que no hay ninguna actualización.
