Dijkstra算法为最短路径图的遍历算法

最短路径问题是图论研究中的一个经典算法问题,旨在寻找图中两个节点或单个节点到其他节点的最短路径。根据问题的不同,算法的具体形式包括:

常用的最短路径算法包括Dijkstra算法、A算法、Bellman-Ford算法、SPFA算法(Bellman-Ford算法的改进版)、Floyd-Warshall算法、Johnson算法和双向BFS算法。本文将重点介绍Dijkstra算法的原理和实现。

Dijkstra算法,译作dykstra算法或Dijkstra算法,由荷兰计算机科学家Ezer dykstra在1956中提出,用于解决加权有向图的单源最短路径问题。所谓单源最短路径问题,是指确定起点,寻找从这个节点到图中任意节点的最短路径。该算法可用于寻找两个城市的最短路径或解决著名的旅行商问题。

问题描述:在无向图中,它是一组图节点和一组节点之间的连接边。假设每条边的权重为,求从顶点到其他节点的最短路径(单源最短路径)。

它是一个加权无向图,图中的顶点分为两组。第一组是找到最短路径的顶点集(由表示)。开始的时候,只有源点。当找到最短路径时,添加新的顶点,直到添加完所有顶点,然后算法结束。第二组是最短路径未定的顶点集合(用表示),随着中间顶点的增加,中间顶点逐渐减少。

以下图为例演示Dijkstra算法的工作流程(从顶点开始):

注意:

01)是已经计算出最短路径的顶点的集合;

02)是尚未计算最短路径的顶点集;

03)表示从顶点到顶点的最短距离是3。

步骤1:选择顶点并添加它们。

第二步:选择顶点并添加它们来更新顶点之间的最短距离。

第三步:选择顶点并添加它们以更新顶点之间的最短距离。

第四步:选择顶点并添加它们来更新顶点之间的最短距离。

步骤5:选择顶点并添加它们以更新顶点之间的最短距离。

第六步:选择顶点并添加它们来更新顶点之间的最短距离。

步骤7:选择顶点并添加它们以更新顶点之间的最短距离。

例:节点号1-7分别代表A、B、C、D、E、F、G。

(s路径& lt最短的。Paths (g,algorithm = "Dijkstra "))输出结果:

(s路径& lt最短的。Paths (g,4,algorithm = "Dijkstra "))输出结果:

示例:

找出从D(4)到G(7)的最短路径:

【1】维基百科,最短路径问题:/yalishadaa/article/details/55827681;

[3]RDocumentation:https://www . RDocumentation . org/packages/RNeo4j/versions/1 . 6 . 4/topics/Dijkstra;

[4]r document:https://www . r document . org/packages/I graph/versions/0.1.1/topics/shortest . paths;

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