floyd算法代码实现

下面是用Python实现Floyd算法的代码，具体内容如下：

# -*- coding: utf-8 -*-
# Created on Thu Jul 13 14:56:37 2017
# author: linzr

## 表示无穷大
INF_val = 9999

class Floyd_Path():
    def __init__(self, graph):
        self.graph = graph
        self.n = len(graph)
        self.dist = [[graph[i][j] for j in range(self.n)] for i in range(self.n)]
        self.path = [[j for j in range(self.n)] for i in range(self.n)]
        self.floyd()

    def floyd(self):
        for k in range(self.n):
            for i in range(self.n):
                for j in range(self.n):
                    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]
                        self.path[i][j] = self.path[i][k]
    def get_path(self, start, end):
        path = []
        while start != end:
            path.append(start)
            start = self.path[start][end]
        path.append(end)
        return path

if __name__ == '__main__':
    graph = [[0, 1, INF_val, 1, 5],
             [9, 0, 3, 2, INF_val],
             [INF_val, INF_val, 0, 4, INF_val],
             [INF_val, INF_val, 2, 0, 3],
             [3, INF_val, INF_val, INF_val, 0]]
    floyd = Floyd_Path(graph)
    print(floyd.get_path(0, 2))

这段代码实现了Floyd算法，可以求出给定图中任意两点之间的最短路径。具体实现过程是：首先将图表示为一个n行n列的矩阵，矩阵中的元素(i,j)表示从节点i到节点j的距离dij，如果两点直接没有边相连，则相应的元素就是无穷(∞)。然后，通过三重循环遍历所有节点，更新每个节点之间的最短路径和路径信息。最后，可以通过get_path方法获取任意两点之间的最短路径。