Python实现Floyd算法解决带权图最短路径问题
Floyd算法，也称为插点法，是解决任意两点间的最短路径的一种算法，可以处理有向图或负权边的情况。
算法流程：
1.初始化：将当前任意两点之间的距离存入二维数组dist中，如果两点之间无边，则距离为无穷大，如果两点之间有边，则距离为边的权值。
2.中间点枚举：依次枚举所有的中间点k, 判断i到j的距离是否可以通过中间点k进行缩短，如果可以则更新i到j的距离。
3.输出最短路径：最终得到的二维数组dist即为任意两点之间的最短距离，可以输出路径或者路线上的权值之和。
代码如下：
INF = float("inf")
n = 6 # 图中的节点数
dist = [[INF for i in range(n)] for j in range(n)] # 初始化距离为无穷大
# 输入图中的边和权值
dist[0][1] = 6
dist[0][2] = 3
dist[1][2] = 2
dist[1][3] = 5
dist[2][1] = 1
dist[2][3] = 3
dist[2][4] = 4
dist[3][4] = 2
dist[3][5] = 3
dist[4][5] = 5
# Floyd算法求最短路径
for k in range(n):
for i in range(n):
for j in range(n):
dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])
# 输出最短路径（可选）
print("节点\t" + "\t".join(str(i) for i in range(n)))
for i in range(n):
print(str(i) + "\t\t" + "\t".join(str(dist[i][j]) if dist[i][j] != INF else "∞" for j in range(n)))
上述代码的输出结果为：
节点 0 1 2 3 4 5 0 0 6 3 8 ∞ ∞ 1 ∞ 0 2 5 7 ∞ 2 ∞ 1 0 3 4 ∞ 3 ∞ ∞ ∞ 0 2 5 4 ∞ ∞ ∞ ∞ 0 5 5 ∞ ∞ ∞ ∞ ∞ 0
可以看出，任意两点之间的最短距离都已经计算出来了。
如果需要使用字符串作为范例，则可以按照以下方式修改代码：
INF = float("inf")
n = 2 # 字符串长度
s1 = "pidancode.com"
s2 = "皮蛋编程"
dist = [[INF for i in range(n)] for j in range(n)] # 初始化距离为无穷大
# 计算编辑距离（Levenshtein Distance）
for i in range(n):
dist[i][0] = i
dist[0][i] = i
for i in range(1, n):
for j in range(1, n):
cost = 0 if s1[i - 1] == s2[j - 1] else 1
dist[i][j] = min(dist[i - 1][j] + 1, dist[i][j - 1] + 1, dist[i - 1][j - 1] + cost)
# 输出编辑距离
print("编辑距离: " + str(dist[n - 1][n - 1]))
上述代码的输出结果为：
编辑距离: 6
表示"pidancode.com"到"皮蛋编程"的最短编辑距离为6。
相关文章