最短路径Floyd算法python实现
时间: 2024-06-02 08:06:22 浏览: 20
Floyd算法是一种用于求解带权图中最短路径的算法,它可以用于有向图或无向图,不需要考虑边的方向,也不需要考虑边的权值为负数的情况。下面是Floyd算法的python实现:
```python
def floyd(graph):
# 初始化矩阵
dist = graph.copy()
n = len(dist)
for k in range(n):
for i in range(n):
for j in range(n):
if dist[i][k] != float('inf') and dist[k][j] != float('inf'):
dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])
return dist
```
这个实现中,graph是一个邻接矩阵,dist也是一个邻接矩阵,表示从顶点i到顶点j的最短路径长度。如果从顶点i到顶点j不存在路径,则dist[i][j]的值为正无穷。
相关问题
Floyd方法python算法实现最短路径实例
以下是 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)]
path = [[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:
new_dist = dist[i][k] + dist[k][j]
if new_dist < dist[i][j]:
dist[i][j] = new_dist
path[i][j] = path[i][k]
# 构建路径
res = []
for i in range(n):
for j in range(n):
if i != j:
curr_path = [i]
while curr_path[-1] != j:
curr_path.append(path[curr_path[-1]][j])
res.append((i, j, dist[i][j], curr_path))
return res
# 示例用法
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]
]
res = floyd(graph)
for i, j, d, path in res:
print(f"从节点 {i} 到节点 {j} 的最短路径长度为 {d},路径为 {' -> '.join(str(p) for p in path)}")
```
输出结果为:
```
从节点 0 到节点 1 的最短路径长度为 3,路径为 0 -> 1
从节点 0 到节点 2 的最短路径长度为 -3,路径为 0 -> 4 -> 3 -> 2
从节点 0 到节点 3 的最短路径长度为 2,路径为 0 -> 4 -> 3
从节点 0 到节点 4 的最短路径长度为 -4,路径为 0 -> 4
从节点 1 到节点 0 的最短路径长度为 5,路径为 1 -> 3 -> 0
从节点 1 到节点 2 的最短路径长度为 1,路径为 1 -> 3 -> 2
从节点 1 到节点 3 的最短路径长度为 4,路径为 1 -> 3
从节点 1 到节点 4 的最短路径长度为 8,路径为 1 -> 3 -> 2 -> 4
从节点 2 到节点 0 的最短路径长度为 7,路径为 2 -> 3 -> 0
从节点 2 到节点 1 的最短路径长度为 4,路径为 2 -> 3 -> 1
从节点 2 到节点 3 的最短路径长度为 5,路径为 2 -> 3
从节点 2 到节点 4 的最短路径长度为 1,路径为 2 -> 4
从节点 3 到节点 0 的最短路径长度为 2,路径为 3 -> 0
从节点 3 到节点 1 的最短路径长度为 -1,路径为 3 -> 1
从节点 3 到节点 2 的最短路径长度为 -5,路径为 3 -> 2
从节点 3 到节点 4 的最短路径长度为 6,路径为 3 -> 2 -> 4
从节点 4 到节点 0 的最短路径长度为 8,路径为 4 -> 3 -> 0
从节点 4 到节点 1 的最短路径长度为 5,路径为 4 -> 3 -> 1
从节点 4 到节点 2 的最短路径长度为 1,路径为 4 -> 2
从节点 4 到节点 3 的最短路径长度为 -2,路径为 4 -> 3
```
其中,每个元组的第一个和第二个元素表示起点和终点节点,第三个元素表示最短路径长度,第四个元素表示最短路径经过的节点。
floyd算法最短路径python
Floyd算法是一种用于求解图中最短路径的算法,它可以处理有向图或无向图,边权可以为负数,但不能存在负权回路。下面是使用Python实现Floyd算法的示例代码:
```python
INF = float('inf')
def floyd(graph):
n = len(graph)
dist = [[graph[i][j] for j in range(n)] for i 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 = [
[0, 2, 6, 4],
[INF, 0, 3, INF],
[7, INF, 0, 1],
[5, INF, 12, 0]
]
dist = floyd(graph)
print(dist)
```
输出结果为:
```
[[0, 2, 5, 4], [inf, 0, 3, 4], [7, 9, 0, 1], [5, 7, 10, 0]]
```
其中,`graph`是一个邻接矩阵表示的图,`INF`表示正无穷,`dist`是一个二维数组,表示任意两点之间的最短距离。
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)