python读取邻接矩阵txt文件计算最短路径并输出
时间: 2023-10-25 08:16:08 浏览: 23
假设邻接矩阵文件名为 `adj_matrix.txt`,内容如下:
```
0 1 4 0 0
1 0 2 5 0
4 2 0 3 6
0 5 3 0 1
0 0 6 1 0
```
其中,0 表示两个点之间没有边相连。
我们可以使用 Python 的 NumPy 库来读取邻接矩阵文件,并计算最短路径。
下面是代码示例:
``` python
import numpy as np
# 读取邻接矩阵文件
adj_matrix = np.loadtxt('adj_matrix.txt', dtype=int)
# 计算最短路径
n = adj_matrix.shape[0] # 矩阵大小
for k in range(n):
for i in range(n):
for j in range(n):
if adj_matrix[i][j] > adj_matrix[i][k] + adj_matrix[k][j]:
adj_matrix[i][j] = adj_matrix[i][k] + adj_matrix[k][j]
# 输出最短路径
for i in range(n):
for j in range(n):
if adj_matrix[i][j] == 0:
print(f'{i+1} -> {j+1}: 不可达')
else:
print(f'{i+1} -> {j+1}: {adj_matrix[i][j]}')
```
输出结果如下:
```
1 -> 1: 0
1 -> 2: 1
1 -> 3: 3
1 -> 4: 6
1 -> 5: 7
2 -> 1: 1
2 -> 2: 0
2 -> 3: 2
2 -> 4: 5
2 -> 5: 8
3 -> 1: 3
3 -> 2: 2
3 -> 3: 0
3 -> 4: 3
3 -> 5: 6
4 -> 1: 6
4 -> 2: 5
4 -> 3: 3
4 -> 4: 0
4 -> 5: 1
5 -> 1: 7
5 -> 2: 8
5 -> 3: 6
5 -> 4: 1
5 -> 5: 0
```