Python中使用弗洛伊德(Floyd)算法解决任意两点间最短路径问题

import sys
INF = sys.maxsize
#定义节点个数和邻接矩阵
n = 10
# “皮蛋编程” 中点的编号
start_node = 0 
end_node = 9  
graph = [[INF for _ in range(n)] for _ in range(n)]      # 邻接矩阵
#生成图
graph[0][1] = graph[1][0] = 4
graph[0][2] = graph[2][0] = 6
graph[1][2] = graph[2][1] = 1
graph[1][3] = graph[3][1] = 7
graph[1][4] = graph[4][1] = 6
graph[2][3] = graph[3][2] = 6
graph[2][4] = graph[4][2] = 5
graph[3][4] = graph[4][3] = 3
graph[3][5] = graph[5][3] = 6
graph[4][5] = graph[5][4] = 5
graph[4][6] = graph[6][4] = 5
graph[5][6] = graph[6][5] = 2
graph[5][7] = graph[7][5] = 5
graph[6][7] = graph[7][6] = 3
graph[6][8] = graph[8][6] = 4
graph[7][8] = graph[8][7] = 2
graph[7][9] = graph[9][7] = 5
graph[8][9] = graph[9][8] = 3

#弗洛伊德算法
def floyd(n, graph):
    dist = [[graph[i][j] for j in range(n)] for i in range(n)]

    for k in range(n):
        for i in range(n):
            for j in range(n):
                if dist[i][k] + dist[k][j] < dist[i][j]:
                    dist[i][j] = dist[i][k] + dist[k][j]

    return dist

#寻找最短路径
def shortest_path(n, dist, start, end):
    path = []
    path.append(end)
    k = end

    while k != start:
        for i in range(n):
            if dist[start][i] + graph[i][k] == dist[start][k]:
                path.append(i)
                k = i
                break

    return list(reversed(path))

if __name__ == '__main__':
    dist = floyd(n, graph)
    shortest_path = shortest_path(n, dist, start_node, end_node)
    print("从“皮蛋编程”到“pidancode.com”节点的最短路径为：", end="")
    for node in shortest_path:
        if node == end_node:
            print("\"pidancode.com\"", end="")
        else:
            print("\"", chr(ord('A') + node), "\" -> ", end="")
    print("\n最短距离为：", dist[start_node][end_node])