最短路径算法之三：多源带权图，Floyd算法，python实现

其他图的最短路径可以看下我的这两篇：

1、求单源无权图的最短路径，BFS算法，python实现

2、求单源带权图最短路径，Dijkstra算法，python实现

求多源带权图最短路径，就是求任意两个顶点的最短路径，常见的实现思路有很多种，这里介绍两种

1. 对图所有顶点循环一遍 Dijkstra，因为一遍Dijkstra可以求到给定一个起点到任意顶点的最短路径，所以循环一遍所有顶点即可以求任意两顶点的最短路径。
2. Floyd算法

Floyd算法介绍

         表示从顶点 Vi 到顶点 Vj 的路径上经过的顶点序号不大于 k 的最短路径长度：

                当k=0时， 表示任意两个结点，仅可能经过顶点0的最短距离

                当k=1时， 表示任意两个结点，仅可能经过顶点0、1的最短距离

                当k=k-1时， 表示任意两个结点，仅可能经过顶点0、1、...、k-1的最短距离

                当k=k时， 表示任意两个结点，全图的最短距离

        可见，当k=顶点数时，我们即可以求得任意两个顶点的全图最短距离，否则只能求到k-i个顶点的最短距离，不是真正的最短距离。

        当 已经完成，递推到时：

                如果 Vi -> Vj 的最短路径不经过 k，那么=

                反之， 如果 Vi -> Vj 的最短路径经过 k，即 { i -> { l<=k } > j } ，那么这条路径必然由两部分组成  

代码实现：

class Floyd(IVisitGraph):
 
    INFINITY = 9999999
 
    def __init__(self):
        super(Floyd, self).__init__()
        self.dist = [[]]  # dist矩阵 存储i->j的最短路径
 
    def initVisted(self, g):
        """
        g: 图，矩阵实现
        """
        super(Floyd, self).initVisted(g)
 
        self.dist = [ [-1 for i in range(g.nV)] for j in range(g.nV)]
 
        for i in range(g.nV):
            for j in range(g.nV):
                if j == i:
                    self.dist[i][j] = 0
                elif g.G[i][j] < 0:  # 没有边的情况下要更新为无穷大，因为选最短路径
                    self.dist[i][j] = self.INFINITY  
                else:  # 有边则更新为权重
                    self.dist[i][j] = g.G[i][j]  
 
    def visit(self, g, v: int):
        """
        佛洛伊德算法，解决图的多源最短路问题
        """
        self.g = g
        # 显然时间复杂度V^3
        for k, v in enumerate(range(g.nV)):
            for i, v in enumerate(range(g.nV)):
                for j, v in enumerate(range(g.nV)):
                    # 是否存在顶点K，导致 i->k->j 才是i->j的最短路径
                    # self.dist[i][j] 上一次 D（k-1) 的最短距离
                    # k 影响因子
                    if (self.dist[i][j] > self.dist[i][k]+self.dist[k][j]):
                        self.dist[i][j] = self.dist[i][k]+self.dist[k][j]

以下图为例，拆分一下 

未开始Dloyd时，进行初始化工作， 为边矩阵，顶点自己到自己的距离为0，其余为邻接边的权重、如果两个顶点之间没有边则设置一个 INFINITY 值。

•  以V1为例，V1到V1 dist为0；V1到V2有边，dist值为2；V1到V3没有边（有向），dist为无穷大.....

现在进行第一次遍历， k=0，，表示仅可能经过顶点V1的最短路径，此时 具体数值如下

• 经过V1后，V3到V2连通了；V3到V4连通了；请注意此时不是最短路径。

现在进行第二次遍历， k=1，，表示仅可能经过顶点V1，V2的最短路径，此时D具体数值如下

• V2加入后，V1到V5连通了；V3到V5也连通了；请注意此时不是最短路径。 

现在进行第三次遍历， k=2，，表示仅可能经过顶点V1，V2，V3的最短路径，此时D具体数值如下

• 看起来没什么变化，因为能和V3连通必须和V4连通，现在V4还没有加进来

现在进行第四次遍历， k=3，，表示仅可能经过顶点V1，V2，V3，V4的最短路径，此时D具体数值如下 

•  随着V4的加入，不少路都连通了，并且路径也变短了。这恰恰说明了只有当k等于顶点数时，才是真正的最短路径，前面的只能说算是“连通路径”

后面不逐步解释了，只是体会一下随着结点的加入，两点之间路径的变化效果。最后展示一下当k=6时，，表示全图的最短路径。此时最短路径如下