floyd算法python
时间: 2023-08-03 17:58:27 浏览: 49
Floyd算法是一种动态规划算法,用于求解图中所有节点之间的最短路径。它的时间复杂度为O(n^3),适用于较小的图。
在Python中,可以使用二维数组来表示图,其中数组元素a[i][j]表示节点i到节点j的距离。如果节点i和节点j之间没有边相连,则a[i][j]的值为无穷大。
以下是Floyd算法的Python实现:
```python
def floyd(graph):
n = len(graph)
dist = [[] * n for i in range(n)]
for i in range(n):
for j in range(n):
dist[i][j] = graph[i][j]
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是一个二维数组,表示图的邻接矩阵。函数返回一个二维数组dist,其中dist[i][j]表示节点i到节点j的最短路径长度。
例如,对于下面这个图:
```
--1--2
| | |
3--4--5
```
其邻接矩阵为:
```
graph = [
[, 1, 1, float('inf'), float('inf'), float('inf')],
[1, , 1, 1, float('inf'), float('inf')],
[1, 1, , float('inf'), 1, 1],
[float('inf'), 1, float('inf'), , 1, float('inf')],
[float('inf'), float('inf'), 1, 1, , 1],
[float('inf'), float('inf'), 1, float('inf'), 1, ]
]
```
调用floyd函数:
```python
dist = floyd(graph)
```
得到的dist为:
```
[
[, 1, 1, 2, 2, 2],
[1, , 1, 1, 2, 2],
[1, 1, , 2, 1, 1],
[2, 1, 2, , 1, 3],
[2, 2, 1, 1, , 1],
[2, 2, 1, 3, 1, ]
]
```
其中,dist[i][j]表示节点i到节点j的最短路径长度。例如,dist[][5]表示节点到节点5的最短路径长度为2。
阅读全文