Algoritmo de recorrido de gráfico camino más corto Algoritmo de Dijkstra

El problema del camino más corto es un problema algorítmico clásico en la investigación de la teoría de grafos, cuyo objetivo es encontrar el camino más corto entre dos nodos o un solo nodo en el gráfico hacia otros nodos. Dependiendo del problema, las formas específicas del algoritmo incluyen:

Los algoritmos de ruta más corta comúnmente utilizados incluyen: algoritmo Dijkstra, algoritmo A, algoritmo Bellman-Ford, algoritmo SPFA (una versión mejorada del algoritmo Bellman-Ford ), algoritmo Floyd-Warshall, algoritmo Johnson y algoritmo BFS bidireccional. Este artículo se centrará en el principio y la implementación del algoritmo de Dijkstra.

El algoritmo de Dijkstra, traducido como algoritmo de Dijkstra o algoritmo de Dijkstra, fue propuesto por el informático holandés Edsgel Dijkstra en 1956 para resolver el problema de ponderación del camino más corto de fuente única para gráficos dirigidos. El llamado problema del camino más corto de fuente única se refiere a determinar el punto de partida y encontrar el camino más corto desde ese nodo a cualquier nodo en el gráfico. El algoritmo se puede usar para encontrar el camino más corto entre dos ciudades o resolver el famoso viajante de comercio. problema.

Descripción del problema: En un grafo no dirigido, es el conjunto de nodos del grafo, y es el conjunto de aristas que conectan los nodos. Suponga que el peso de cada borde es , encuentre el camino más corto desde el vértice hasta los nodos restantes (camino más corto de fuente única).

Es un gráfico no dirigido ponderado. Los vértices del gráfico se dividen en dos grupos. El primer grupo es el conjunto de vértices para los que se ha encontrado el camino más corto (representado por). Inicialmente solo hay puntos de origen. Cuando se encuentra una ruta más corta, se agregan nuevos vértices hasta que se agregan todos los vértices y el algoritmo finaliza. El segundo grupo es el conjunto de vértices de ruta más corta indeterminados (representados por ). A medida que aumenta el número de vértices, el número de vértices disminuye gradualmente.

Tome la siguiente figura como ejemplo para demostrar el flujo de trabajo del algoritmo de Dijkstra (tomando el vértice como punto de partida):

Nota:

01) es el más corto El conjunto de vértices del camino;

02) es el conjunto de vértices para los cuales no se ha calculado el camino más corto

03) significa que la distancia más corta desde el vértice; al vértice es 3

Paso 1: Seleccione los vértices para agregar

Paso 2: Seleccione los vértices para agregar; se actualiza la distancia más corta entre los vértices

Paso 3: Seleccione los vértices para agregar, se actualiza la distancia más corta entre los vértices

Paso 4: Seleccione el vértice y agréguelo, y actualice la distancia más corta entre los vértices

Paso 5: Seleccione el vértice y agréguelo, y actualice la distancia más corta entre los vértices

Paso 6 Paso: Seleccione los vértices a agregar y la distancia más corta entre los vértices en la actualización

Paso 7: Seleccione los vértices para agregar y la distancia más corta entre los vértices en la actualización

Ejemplo: los números de nodo 1-7 representan A, B, C, D, E, F, G

(s.paths lt; - short.paths(g, algoritmo = "dijkstra")) Resultados de salida:

( s.paths lt; -short.paths(g, 4, algoritmo = "dijkstra")) Resultados de salida:

Ejemplo:

Encuentre D(4) a G(7) El camino más corto:

[1] Wikipedia, problema del camino más corto: /yalishadaa/article/details/55827681;

[3]RDocumentación: https://www.rdocumentation/packages/RNeo4j/versions/1.6.4/topics/dijkstra. ;

[4]RDocumentación: https://www.rdocumentation.org/packages/igraph/versions/0.1.1/topics/shortity.paths;

[5]Pypi : https://pypi.org/project/Dijkstar/