多源最短路径算法–Floyd算法

多源最短路径算法–Floyd算法

Floyd算法是为了求出每一对顶点之间的最短路径

它使用了动态规划的思想，将问题的求解分为了多个阶段

先来个例子，这是个有向图

Floyd算法的运行需要两个矩阵

最短路径矩阵

从当前这个状态看各顶点间的最短路径长度

例如初始状态

可以看出这是该有向图的邻接矩阵

顶点之间中转点矩阵

初始状态都没有中转点

引入中转点

A^(k-1)代表引入顶点k-1时，各个顶点的最短路径状态

path^(k-1)代表引入顶点k-1后，各个顶点的最短路径需要经过哪个结点

判断顶点i到顶点j，如果经过顶点k，是否会更短？

如果更短，改变A^(k-1)数组中i结点到j结点的最短路径，同时更改path^(k)数组，表明经过顶点k，顶点i到顶点j路径更短

1. 允许在V₀中转，计算出当前的最短路径

顶点2到顶点1

可以看到原来顶点2到顶点1是没有路径的，通过V₀之后,最短路径变为11，那么更新A⁽⁰⁾数组，A⁽⁰⁾数组代表引入V₀之后个顶点之间的最短路径，同是更新path⁽⁰⁾数组，代表V₂到V₁经过了V₀

2. 允许在V₀,V₁中转，计算出当前的最短路径

顶点0到顶点2

可以看到原来顶点0到顶点2的距离是13，通过V₁之后,最短路径变为10，那么更新A⁽¹⁾数组，A^（1)数组代表引入V₁之后个顶点之间的最短路径，同是更新path⁽¹⁾数组，代表V₀到V₂经过了V₁

3. 允许在V₀,V₁,V₂中转，计算出当前的最短路径

顶点1到顶点0

可以看到原来顶点1到顶点0的距离是10，通过V₁之后,最短路径变为9，那么更新A⁽²⁾数组，A^（2)数组代表引入V₂之后个顶点之间的最短路径，同是更新path⁽²⁾数组，代表V₁到V₀经过了V₂

4. 最终结果

5. 核心代码

再看一个新的例子

1. 允许在V₀中转，k=0

所有结点之间都不能通过V₀获得更短的路径，故不更新A⁽⁰⁾数组和path⁽⁰⁾数组

2. 允许在V₀,V₁中转，k=1

V₂到V₃和V₂到V₄经过V₀,V₁中转有更短的路径，故更新A⁽¹⁾数组和path⁽¹⁾数组

3. 允许在V₀,V₁,V₂中转，k=2

V₀到V₁，V₀到V₃，V₀到V₄经过V₀,V₁,V₂中转有更短的路径，故更新A⁽²⁾数组和path⁽²⁾数组

4. 允许在V₀,V₁,V₂,V₃中转，k=3

V₀到V₄，V₁到V₄，V₂到V₄经过V₀,V₁,V₂,V₃中转有更短的路径，故更新A⁽³⁾数组和path⁽³⁾数组

5. 允许在V₀,V₁,V₂,V₃,V₄中转，k=4

所有结点之间都不能通过V₄获得更短的路径，故不更新A⁽⁴⁾数组和path⁽⁴⁾数组

注意

1. Floyd算法不能解决带有“负权回路”的图，这种图可能没有最短路径