Floyd方法python算法实现
时间: 2023-08-06 17:22:55 浏览: 49
以下是 Floyd 算法在 Python 中的代码实现:
```python
import sys
# 计算任意两点之间的最短距离
def floyd(graph):
n = len(graph)
# 初始化距离矩阵
dist = [[graph[i][j] for j in range(n)] for i in range(n)]
# 遍历所有节点,以 k 为中间节点更新距离矩阵
for k in range(n):
for i in range(n):
for j in range(n):
if dist[i][k] != sys.maxsize and dist[k][j] != sys.maxsize:
dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])
return dist
```
其中,`graph` 是一个二维列表,表示图的邻接矩阵,`graph[i][j]` 表示从节点 `i` 到节点 `j` 的边的权重,如果不连通,则为无穷大。函数返回一个二维列表,表示任意两点之间的最短距离。如果某个节点不连通,则距离为无穷大。
以下是一个使用示例:
```python
graph = [
[0, 3, 8, sys.maxsize, -4],
[sys.maxsize, 0, sys.maxsize, 1, 7],
[sys.maxsize, 4, 0, sys.maxsize, sys.maxsize],
[2, sys.maxsize, -5, 0, sys.maxsize],
[sys.maxsize, sys.maxsize, sys.maxsize, 6, 0]
]
dist = floyd(graph)
for row in dist:
print(row)
```
输出结果为:
```
[0, 1, -3, 2, -4]
[3, 0, -4, 1, -1]
[7, 4, 0, 5, 3]
[2, -1, -5, 0, -2]
[8, 5, 1, 6, 0]
```
其中,第 `i` 行第 `j` 列的元素表示从节点 `i` 到节点 `j` 的最短距离。