Algoritmo de Dijkstra
El algoritmo de Dijkstra es un algoritmo típico de ruta más corta de fuente única, que se utiliza para calcular las rutas más cortas desde un nodo a todos los demás nodos. La característica principal es que se expande capa por capa desde el punto inicial hasta llegar al punto final. Tenga en cuenta que este algoritmo requiere que no haya bordes de peso negativos en el gráfico.
Supongamos que G=(V,E) es un gráfico dirigido ponderado. Divida el conjunto de vértices V en el gráfico en dos grupos. El primer grupo es el conjunto de vértices para el que se ha encontrado el camino más corto (representado). por S, inicialmente solo hay un punto de origen en S. Cada vez que se encuentra una ruta más corta, se agregará al conjunto S. Hasta que se agreguen todos los vértices a S, el algoritmo finaliza (el segundo grupo es el restante). caminos más cortos que no se han determinado. Conjunto de vértices (representado por U), agregue el segundo grupo de vértices a S en orden creciente de longitud del camino más corto. Durante el proceso de unión, la longitud del camino más corto desde el punto fuente v hasta cada vértice en S siempre se mantiene sin que sea mayor que la longitud del camino más corto desde el punto fuente v hasta cualquier vértice en U. Además, cada vértice corresponde a una distancia. La distancia del vértice en S es la longitud del camino más corto desde v hasta este vértice. La distancia del vértice en U es el camino actual desde v hasta este vértice que solo incluye los vértices en. S como vértices intermedios. La longitud del camino más corto.
(1) Inicialmente, S solo contiene el punto inicial D; U contiene otros vértices excepto D, y la distancia de los vértices en U es "la distancia desde el punto inicial D hasta el vértice" (para Por ejemplo, el vértice en U La distancia de A es la longitud de [D, A], y luego D y A no son adyacentes, entonces la distancia de A es ∞)
(2) Seleccione "el vértice K con la distancia más corta" desde U, y agregue el vértice K a S; al mismo tiempo, elimine el vértice K de U
(3) Actualice la distancia desde cada vértice en U hasta el punto inicial D . La razón por la cual se actualiza la distancia de los vértices en U es porque en el paso anterior se determinó que K es el vértice para encontrar el camino más corto, por lo que K puede usarse para actualizar las distancias desde otros vértices hasta el punto inicial D ( por ejemplo, la distancia de [D, A] puede ser mayor que la distancia [D,K]+[K,A])
(4) Repita los pasos (2) y (3) hasta que todos los vértices han sido atravesados
/yalishadaa/article /details/55827681