转自https://www.cnblogs.com/wsw-seu/p/8185285.html
1、单源点的最短路径问题:给定带权有向图G和源点v,求从v到G中其余各顶点的最短路径。
我们用一个例子来具体说明迪杰斯特拉算法的流程。
定义源点为 0,dist[i]
为源点 0 到顶点 i 的最短路径。其过程描述如下:
步骤 | dist[1] | dist[2] | dist[3] | dist[4] | 已找到的集合 |
---|---|---|---|---|---|
第 1 步 | 8 | 1 | 2 | +∞ | {2} |
第 2 步 | 8 | × | 2 | 4 | {2, 3} |
第 3 步 | 5 | × | × | 4 | {2, 3, 4} |
第 4 步 | 5 | × | × | × | {2, 3, 4, 1} |
第 5 步 | × | × | × | × | {2, 3, 4, 1} |
第 1 步:从源点 0 开始,找到与其邻接的点:1,2,3,更新dist[]
数组,因 0 不与 4 邻接,故dist[4]
为正无穷。在dist[]
中找到最小值,其顶点为 2,即此时已找到 0 到 2 的最短路。
第 2 步:从 2 开始,继续更新dist[]
数组:2 与 1 不邻接,不更新;2 与 3 邻接,因0→2→3
比dist[3]
大,故不更新dist[3]
;2 与 4 邻接,因0→2→4
比dist[4]
小,故更新dist[4]
为 4。在dist[]
中找到最小值,其顶点为 3,即此时又找到 0 到 3 的最短路。
第 3 步:从 3 开始,继续更新dist[]
数组:3 与 1 邻接,因0→3→1
比dist[1]
小,更新dist[1]
为 5;3 与 4 邻接,因0→3→4
比dist[4]
大,故不更新。在dist[]
中找到最小值,其顶点为 4,即此时又找到 0 到 4 的最短路。
第 4 步:从 4 开始,继续更新dist[]
数组:4 与 1 不邻接,不更新。在dist[]
中找到最小值,其顶点为 1,即此时又找到 0 到 1 的最短路。
第 5 步:所有点都已找到,停止。
2、弗洛伊德算法:
1)算法思想原理:
Floyd算法是一个经典的动态规划算法。用通俗的语言来描述的话,首先我们的目标是寻找从点i到点j的最短路径。从动态规划的角度看问题,我们需要为这个目标重新做一个诠释(这个诠释正是动态规划最富创造力的精华所在)
从任意节点i到任意节点j的最短路径不外乎2种可能,1是直接从i到j,2是从i经过若干个节点k到j。所以,我们假设Dis(i,j)为节点u到节点v的最短路径的距离,对于每一个节点k,我们检查Dis(i,k) + Dis(k,j) < Dis(i,j)是否成立,如果成立,证明从i到k再到j的路径比i直接到j的路径短,我们便设置Dis(i,j) = Dis(i,k) + Dis(k,j),这样一来,当我们遍历完所有节点k,Dis(i,j)中记录的便是i到j的最短路径的距离。
2).算法描述:
a.从任意一条单边路径开始。所有两点之间的距离是边的权,如果两点之间没有边相连,则权为无穷大。
b.对于每一对顶点 u 和 v,看看是否存在一个顶点 w 使得从 u 到 w 再到 v 比己知的路径更短。如果是更新它。