python Floyd

Floyd算法是一种用于寻找给定加权图中多源点之间最短路径的算法，该算法利用了动态规划的思想。它的实现可以使用Python编程语言。以下是一个示例代码 ：

n = 4
INFINITY = 100000.0

# 距离矩阵
D = [[0, 2, 6, 4],
     [INFINITY, 0, 3, INFINITY],
     [7, INFINITY, 0, 1],
     [5, INFINITY, 12, 0]]

# 路径矩阵
P = [[0, 0, 0, 0],
     [0, 0, 0, 0],
     [0, 0, 0, 0],
     [0, 0, 0, 0]]

# 初始化路径矩阵，即P[u][v 记录直达路径uv的终点v前面的顶点u
for u in range(0, n):
    for v in range(0, n):
        P[u][v = u

print("初始状态：")
print("距离矩阵为:", *D, sep="\n")
print("路径矩阵为:", *P, sep="\n")

for w in range(0, n):
    for u in range(0, n):
        for v in range(0, n):
            if w != u and w != v and D[u][w + D[w][v < D[u][v]:
                D[u][v = D[u][w + D[w][v]
                P[u][v = P[w][v]

print("排序后:")
print("距离矩阵为:", *D, sep="\n")
print("路径矩阵为:", *P, sep="\n")

根据路径矩阵P，可以追踪到任何一对顶点u和顶点v之间的路径。下面是示例代码，用于将路径从终点倒过来追踪到起点：

for u in range(0, n):
    for v in range(0, n):
        if u == v:
            continue
        print("{}到{}的逆向路径是:".format(u, v), end=' ')
        print(v, end=',') # 先输出终点
        w = P[u][v # 推到上一个节点
        while w != u:
            print(w, end=',')
            w = P[u][w # 推到u-->w的上一个节点
        print(u)

综上所述，以上是Python实现Floyd算法的代码，可以用来计算给定加权图中多源点之间的最短路径。<span class="em">1</span><span class="em">2</span><span class="em">3</span><span class="em">4</span>