写一段python的代码内容是Floyd算法
时间: 2024-04-10 10:33:01 浏览: 86
python实现Floyd算法
5星 · 资源好评率100%
当然,以下是用Python编写的Floyd算法的代码示例:
```python
# 定义一个无穷大的常量
INF = float('inf')
def floyd(graph):
# 获取图中顶点的个数
num_vertices = len(graph)
# 初始化距离矩阵
distance = [[0 if i == j else graph[i][j] if graph[i][j] != 0 else INF for j in range(num_vertices)] for i in range(num_vertices)]
# 通过中间顶点依次更新距离矩阵
for k in range(num_vertices):
for i in range(num_vertices):
for j in range(num_vertices):
if distance[i][j] > distance[i][k] + distance[k][j]:
distance[i][j] = distance[i][k] + distance[k][j]
return distance
# 测试代码
graph = [[0, 5, INF, 10],
[INF, 0, 3, INF],
[INF, INF, 0, 1],
[INF, INF, INF, 0]]
result = floyd(graph)
for row in result:
print(row)
```
这段代码实现了Floyd算法,用于计算给定图中任意两个顶点之间的最短路径。在示例中,我们使用一个邻接矩阵来表示图,其中INF表示两个顶点之间不存在直接连接。输出结果是一个距离矩阵,其中的值表示对应顶点之间的最短路径长度。
阅读全文