使用Dijkstra/Floyd算法解决最短路径问题

一，最短路径问题抽象

典型用途： 交通网络问题（从甲地到乙地是否有公路连通？哪一条路是最短的？）

交通网络用有向网来表示：

• 顶点 — 表示地点；
• 弧 — 表示两个地点之间有路连通；
• 弧上的权值 — 表示两地之间的距离、交通费或途中所花费的时间等。

如何能够使运输时间最短或运费最少？这就是一个求两个地点间的最短路径问题。

问题抽象： 在有向网中 A 点（源点）到达 B 点（终点）的多条路径中，寻找一条各边权值之和最小的路径，即最短路径。

！！！注意！！！

最短路径与最小生成树不同，
路径上不一定包含 n 个顶点，
也不一定包含 n-1 条边。

1.1 单源（两点之间）最短路径 - Dijkstra算法

视频讲解：6.6.2最短路径2–Dijkstra算法
ps：有时间的话建议看一下上边的视频讲解。

单源最短路径（Single-Source Shortest Paths） — 使用 Dijkstra（地杰斯特拉）算法


步骤总结：

• 选择起始点，分别记录该点到所有与其邻接的（直达）顶点的距离，并选择距离最短段的顶点作为转接点，即为 v_j；
• 将 v_j 加入路径，并记录加入该点后可以到达的顶点和距离，并选出最短距离，并记录到达的点为下一个转接点；
• 重复上述操作，直至访问过所有的顶点。

1.2 某源点到其他各点的最短路径 - Floyd算法

视频参考：6.6.2最短路径3–Floyd算法

所有顶点间的最短路径

• 方法1：依次以所有顶点为源点，重复执行 Dijkstra算法 n 次；
• 方法2：使用 Floyd（弗洛伊德）算法。

Floyd（弗洛伊德）算法思想

• 逐个顶点试探；
• 从 v_i 到 v_j 的所有可能存在的路径中；
• 选出一条长度最短的路径。

例，采用Floyd算法，求图中各项顶点之间最短路径