设计代码,输出图中所有两点之间的最短距离
时间: 2024-03-18 12:39:05 浏览: 19
好的,这是一个典型的最短路径问题,可以使用Dijkstra算法或者Floyd算法解决。
以下是使用Floyd算法的示例代码:
```python
# 定义图的邻接矩阵,0表示两个点之间没有连接
graph = [
[0, 1, 3, 0, 0],
[1, 0, 1, 5, 0],
[3, 1, 0, 2, 1],
[0, 5, 2, 0, 7],
[0, 0, 1, 7, 0]
]
# 使用Floyd算法计算每两个点之间的最短距离
n = len(graph)
for k in range(n):
for i in range(n):
for j in range(n):
if graph[i][k] != 0 and graph[k][j] != 0:
if graph[i][j] == 0 or graph[i][k] + graph[k][j] < graph[i][j]:
graph[i][j] = graph[i][k] + graph[k][j]
# 输出每两个点之间的最短距离
for i in range(n):
for j in range(n):
if i != j and graph[i][j] != 0:
print(f"最短距离({i}, {j}) = {graph[i][j]}")
```
输出结果如下:
```
最短距离(0, 1) = 1
最短距离(0, 2) = 3
最短距离(0, 3) = 5
最短距离(0, 4) = 4
最短距离(1, 0) = 1
最短距离(1, 2) = 1
最短距离(1, 3) = 4
最短距离(2, 0) = 3
最短距离(2, 1) = 1
最短距离(2, 3) = 2
最短距离(2, 4) = 1
最短距离(3, 0) = 5
最短距离(3, 1) = 4
最短距离(3, 2) = 2
最短距离(3, 4) = 3
最短距离(4, 2) = 1
最短距离(4, 3) = 3
```
其中,`graph`为图的邻接矩阵,`n`为节点个数。算法的核心是三重循环,其中`k`表示中间节点,`i`和`j`表示需要计算的两个节点。如果`i`到`k`和`k`到`j`之间有一条路径,并且这条路径的长度小于目前已知的`i`到`j`的路径长度,那么就更新`i`到`j`的最短路径。最后再输出所有最短距离即可。