FLOYD算法python
时间: 2023-11-07 19:15:27 浏览: 45
Floyd算法是一种用于求解图中最短路径的算法。下面是一个使用Python实现Floyd算法的示例代码:
```python
INF = float('inf')
def floyd(graph):
n = len(graph)
dist = [[0 if i == j else INF for j in range(n)] for i in range(n)]
for i in range(n):
for j in range(n):
if graph[i][j] != 0:
dist[i][j] = graph[i][j]
for k in range(n):
for i in range(n):
for j in range(n):
if dist[i][k] + dist[k][j] < dist[i][j]:
dist[i][j] = dist[i][k] + dist[k][j]
return dist
# 示例使用
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)
```
在这个示例中,我们通过一个邻接矩阵表示图的连接情况。其中,INF表示两点之间没有直接连接,0表示两点之间存在直接连接,其他数字表示连接的权重。算法会返回一个新的邻接矩阵,其中每个元素表示对应点对之间的最短路径长度。