Python中使用Floyd算法求全源最短路径

INF = float('inf') # 无穷大

def floyd(graph):
    n = len(graph)
    dist = [[INF] * n for _ in range(n)] # 初始化距离矩阵
    for i in range(n):
        dist[i][i] = 0 # 自身到自身距离为0
        for j in range(n):
            if graph[i][j] != 0:
                dist[i][j] = graph[i][j] # 相邻节点之间的距离

    for k in range(n):
        for i in range(n):
            for j in range(n):
                if dist[i][j] > dist[i][k] + dist[k][j]:
                    dist[i][j] = dist[i][k] + dist[k][j] # 更新最短路径

    return dist

# 示例
graph = [[0, 3, 8, INF, -4],
         [INF, 0, INF, 1, 7],
         [INF, 4, 0, INF, INF],
         [2, INF, -5, 0, INF],
         [INF, INF, INF, 6, 0]]
dist = floyd(graph)

# 打印最短距离矩阵
for i in range(len(dist)):
    for j in range(len(dist[i])):
        if dist[i][j] == INF:
            print("INF", end="\t")
        else:
            print(dist[i][j], end="\t")
    print()