单源最短路径问题基于Dijkstra算法

Dijkstra算法核心思想解析

带权图最短路径分析

在图结构中，从某一特定起点至另一终点的路径中，若存在一条边权重总和最小的路线，则该路线被定义为最短路径。

1. 针对单一源点至其他所有节点的最短路径问题，可采用迪杰斯特拉算法（Dijkstra）进行求解。
2. 对于图中任意两顶点间的最短路径计算，通常运用弗洛伊德算法（Floyd）来实现。

Dijkstra算法应用与优化

基本思想：按照路径长度由小到大的顺序依次确定各条最短路径。

路径长度最短的最短路径的特性：在该路径中，必然仅包含一条边，并且这条边的权重为所有边中最小值。（记作v0→vK）

接下来路径长度次短的最短路径的特性：
它可能呈现两种情形：要么是源点直接连接至目标点Vi（仅含一条边）；要么是源点先到达顶点VK，再由VK连接至Vi（包含两条边）。

再下一条路径长度次短的最短路径特征：
它也可能存在两种可能性：要么是源点直接抵达该节点（仅含一条边）；要么是源点通过顶点VK、Vi等中间节点逐步到达该节点（由多条边构成）。

其余各条最短路径的特征：
它可能是源点直接连接至该节点（仅含一条边），也可能是源点经过已经确定最短路径的顶点，最终抵达该节点。

例子：

![在这里插入图片描述](https://ad.itadn.com/c/weblog/b