利用Python写出完整的、可运行的、代码尽可能简单易懂的floyd算法
时间: 2024-02-07 07:02:51 浏览: 22
好的,下面是Python实现的Floyd算法代码:
```python
INF = float('inf')
# 以邻接矩阵形式表示图
graph = [
[0, 2, INF, 4],
[2, 0, 5, INF],
[INF, 5, 0, 6],
[4, INF, 6, 0]
]
# Floyd算法实现
def floyd(graph):
n = len(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][j] > dist[i][k] + dist[k][j]:
dist[i][j] = dist[i][k] + dist[k][j]
return dist
# 执行算法并输出结果
dist = floyd(graph)
for row in dist:
print(row)
```
以上代码中,我们先定义了一个表示图的邻接矩阵,然后通过Floyd算法计算出了任意两点之间的最短路径。在代码实现中,我们使用了一个`dist`二维数组来表示距离矩阵,其中`dist[i][j]`表示从顶点i到顶点j的最短路径长度。算法的核心部分就是三重循环,用来更新距离矩阵中的元素。最后,我们将距离矩阵输出,得到每对顶点之间的最短路径长度。