一，Some basic concepts：shortest path problem

二，Variants of shortest path

① Single-source shortest paths（单源最短路径）

➤ 定义：

给定一个起点 sss，要求从 sss 出发，找到它到图中所有其他点 v∈Vv \in Vv∈V 的最短路径。

➤ 应用：

• 地图导航：从当前位置到所有目的地的最短路线

• 网络广播：从某个服务器广播数据到所有客户端

➤ 典型算法：

• Dijkstra（适用于非负权图）

• Bellman-Ford（可处理负权边）

---

② Single-destination shortest paths（单终点最短路径）

➤ 定义：

给定一个终点 ttt，找出图中所有点 vvv 到 ttt 的最短路径。

➤ 技巧：

只需将图中所有边的方向反转，再使用单源最短路径算法即可！

➤ 应用：

• 所有客户前往某家门店的最短路线

• 汇集型路由问题

---

③ Single-pair shortest path（单对最短路径）

➤ 定义：

给定一对顶点 uuu、vvv，只求出这两点之间的最短路径。

➤ 应用：

• 导航系统查询“从 A 地到 B 地怎么走”

• 路由器确定某两台设备的通信最短路径

➤ 算法选择：

虽然可以用 Dijkstra 或 Floyd 算，但由于只需算一对点，使用 A* 等启发式搜索算法通常更高效。

---

④ All-pairs shortest paths（全对最短路径）

➤ 定义：

对图中每一对顶点 u,vu, vu,v，都要求出它们之间的最短路径。

➤ 应用：

• 社交网络分析：任意两人之间的“关系最短路径”

• 网络中全节点间最小通信代价计算

➤ 典型算法：

• Floyd-Warshall（适用于小图）

• Johnson's Algorithm（适合稀疏图）

三，Optimal Substructure (最优子结构定理)

在一个加权、有向图 G=(V,E) 中，如果我们已经知道从顶点 v1 到顶点 vk 的最短路径p=⟨v1,v2,…,vk⟩，那么这个路径的任意子路径 pij=⟨vi,vi+1,…,vj⟩也是从 vi 到 vj 的最短路径。

四，unweighted graph 的 shortest path

①问题描述：

一个无权图，定义一个起始点，如何记录所有点到起始点的最短距离？解法：广度优先搜索（BFS）

②伪代码思路：

1，创建一个队列

2，初始化所有顶点的距离为无穷大，起始顶点的距离是0，将起始顶点入队。

3，遍历：如果起始队列不是空的，那么先将最前面的顶点出队。对于这个顶点相邻的顶点，如果他们的距离是无穷（说明还没被遍历过），那么就把他们的距离变成刚才这个出队的顶点的距离加一（此时距离不是无穷了，也就意味着被遍历过了），然后让这个相邻的顶点入队。

4，然后依次处理队列里面最前面的顶点。

③伪代码时间复杂度

图的顶点数为 ∣V∣，边数为 ∣E∣。广度优先搜索的时间复杂度主要由以下两部分组成：

顶点的处理：每个顶点最多被访问一次。
边的处理：每条边最多被检查一次。

因此，总的时间复杂度是 O(∣V∣+∣E∣)。

五，Weighted graph 的 shortest path：Dijkstra’s algorithm

①迭代思路理解【做题角度】：

purpose：定义一个起始点，要找到所有点的最短路径长度以及这个路径。

1，总体思路和无权图的shortest path 问题差不多，唯一的变化就是这个图是有权重的。

2，先定义一个初始顶点，这个初始顶点的距离定义为0，其他顶点的距离定义为正无穷。由于目前顶点距离最小的点是初始顶点（每一个点都标有对应的距离），所以我们给初始顶点做上标记。

3，对于这个标记点，我们开始遍历与这个标记点相连的没有被标记过的顶点，对于每一个相邻的顶点，如果【标记点的距离+1】小于目前相连顶点的距离值，那么更新这个相连顶点的距离值，并且更新相连顶点的父亲。

4，遍历完所有相邻顶点之后。在剩下没有被标记的顶点里面，挑选一个顶点距离最小的顶点做上标记，重复步骤23。

②伪代码