Algoritmo de Dijkstra en un gráfico ponderado y orientado en más de 128 palabras

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:

Puesta en marcha del algoritmo
El arco saliente A-B se libera, la distancia es 15, 15 siendo un mejor valor que el infinito actualizamos la etiqueta B con 15
El arco saliente A-C se libera la distancia 4 siendo mejor que el infinito actualizamos la etiqueta de la parte superior C
La siguiente parte superior del algoritmo es la que aún no se ha visitado y tiene la etiqueta con el valor más bajo. Aquí es la parte superior c con el valor 4.On
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.
Se libera el Arco C-D saliente, la distancia calculada desde la parte superior A es 4 – 2 – 6. 6 siendo mejor que el infinito actualizamos la etiqueta de la parte superior D.

En el siguiente paso visitamos la cumbre D porque su valor es el más bajo del gráfico
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.
El B-top se procesa: el arco B-E saliente se libera, la distancia de 15 -5 -20 es mayor que el valor de 9 de la cumbre E no hay actualización y el algoritmo termina.