Algoritmo de ruta más corta (Dijkstra)

El algoritmo de Dijkstra es un algoritmo utilizado para resolver la ruta más corta desde una única fuente, requiriendo que el peso de la ruta no sea negativo. Este algoritmo utiliza búsqueda en profundidad y algoritmos codiciosos.

El siguiente es un gráfico ponderado para encontrar el camino más corto desde A a cada nodo.

Paso 1: comenzando desde el punto A, determine la ruta desde cada punto hasta el punto A (si el punto no se puede conectar directamente al punto A, el valor de la distancia es infinito; si el punto se puede conectar directamente a punto A, entonces el valor de la distancia es infinito), después del cálculo, coloree el punto A. El resultado se muestra a continuación:

Paso 2: Encuentre el punto C más cercano al punto A desde puntos distintos. punto A. Desde C A partir del punto, busque sus nodos adyacentes (excepto los puntos coloreados) y vuelva a calcular el valor del punto adyacente del punto C desde el punto A, como el punto B en la figura. valor del punto C al punto A + punto C La ruta a este punto) es menor que el valor original, luego el valor se actualiza a 5 y los puntos D y E se actualizan de manera similar. También marque C como procesado y coloréelo como se muestra.

Paso 3: Encuentra el punto B más cercano a A entre los nodos coloreados y repite el paso 3.

Paso 4: Repita los pasos 3 y 2 hasta que todos los nodos estén coloreados.

Finalmente se calcula la distancia más corta desde el punto A a todos los puntos.

pregunta leetcode 743