Floyd算法的代码实现
时间: 2024-07-28 08:00:18 浏览: 36
Floyd算法,也被称为Floyd-Warshall算法,是一个用于寻找所有顶点对之间最短路径的动态规划方法。它通常用于解决图中的最短路径问题,特别是当图中存在负权重边时。以下是使用Python实现的一个简单版本:
```python
def floyd_warshall(graph):
n = len(graph)
# 初始化距离矩阵,包括自环的最短距离为0
dist = [[graph[u][v] if u != v else 0 for v in range(n)] for u 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
# 使用示例:
# graph是一个二维数组,表示图的邻接矩阵,其中graph[i][j]表示从顶点i到顶点j的距离(如果不存在边,则为无穷大)
graph = [[0, 4, float('inf'), 2],
[4, 0, 8, 5],
[float('inf'), 8, 0, 1],
[2, 5, 1, 0]]
result = floyd_warshall(graph)
# 输出结果是每个顶点对之间的最短路径
print("All-pairs shortest paths:")
for i in range(len(result)):
print(f"From {i}: {result[i]}")