python实现Floyd算法

以下是Python实现Floyd算法的代码，具体解释已在代码中注释：

# -*- coding: utf-8 -*-
# 无穷大的值
INF_val = 9999

class Floyd_Path():
    def __init__(self, graph):
        self.graph = graph
        self.n = len(graph)
        # 初始化路径矩阵
        self.path = [[0 for i in range(self.n)] for j in range(self.n)]
        for i in range(self.n):
            for j in range(self.n):
                if i != j and self.graph[i][j] != INF_val:
                    self.path[i][j] = i
                else:
                    self.path[i][j] = -1
        # Floyd算法
        for k in range(self.n):
            for i in range(self.n):
                for j in range(self.n):
                    if self.graph[i][j] > self.graph[i][k] + self.graph[k][j]:
                        self.graph[i][j] = self.graph[i][k] + self.graph[k][j]
                        self.path[i][j] = self.path[k][j]

    # 获取最短路径
    def get_path(self, i, j):
        if self.path[i][j] == 0:
            return []
        path = [j]
        while i != j:
            j = self.path[i][j]
            path.append(j)
        return path[::-1]

# 测试
if __name__ == '__main__':
    graph = [
        [0, 1, 3, INF_val],
        [1, 0, 1, INF_val],
        [3, 1, 0, 2],
        [INF_val, INF_val, 2, 0]
    ]
    floyd = Floyd_Path(graph)
    print(floyd.graph)
    print(floyd.get_path(0, 3)) # 输出：[0, 1, 2, 3]