在矩阵A=[[0,5,inf,inf,inf,inf,inf], [5,0,inf,3,3,inf,inf], [inf,inf,0,inf,inf,inf,inf], [inf,3,inf,0,inf,inf,inf], [inf,3,inf,inf,0,1,inf], [inf,inf,inf,inf,1,0,2], [inf,inf,inf,inf,inf,2,0]]中,分别改变第3行第四列的值为6、第1行第3列值为5、第2行第3列值为7、第4行第6列值为4等,求出改变某个元素后矩阵的最短距离,将改变前的矩阵最短距离分别与改变后的矩阵最短距离求差,若改变前矩阵的最短距离为无穷,改变后两点间线路为数值,则最短距离差为改变后两点间距离减0,求出最短距离差的总和,找出缩短距离最大、第二大的添加的线路 python代码
时间: 2024-01-08 20:04:47 浏览: 69
Python 实现将numpy中的nan和inf,nan替换成对应的均值
以下是实现该功能的 Python 代码:
```python
import numpy as np
import copy
# 原始矩阵
A = np.array([[0,5,np.inf,np.inf,np.inf,np.inf,np.inf],
[5,0,np.inf,3,3,np.inf,np.inf],
[np.inf,np.inf,0,np.inf,np.inf,np.inf,np.inf],
[np.inf,3,np.inf,0,np.inf,np.inf,np.inf],
[np.inf,3,np.inf,np.inf,0,1,np.inf],
[np.inf,np.inf,np.inf,np.inf,1,0,2],
[np.inf,np.inf,np.inf,np.inf,np.inf,2,0]])
# 改变某个元素后的矩阵
A1 = copy.deepcopy(A)
A1[2][3] = 6
A2 = copy.deepcopy(A)
A2[0][2] = 5
A3 = copy.deepcopy(A)
A3[1][2] = 7
A4 = copy.deepcopy(A)
A4[3][5] = 4
A_list = [A1, A2, A3, A4]
# Floyd算法求最短距离
def floyd(A):
n = A.shape[0]
for k in range(n):
for i in range(n):
for j in range(n):
if A[i][j] > A[i][k] + A[k][j]:
A[i][j] = A[i][k] + A[k][j]
return A
# 计算最短距离差
def calc_diff(A1, A2):
n = A.shape[0]
dist1 = floyd(A1)
dist2 = floyd(A2)
diff_sum = 0
max_diff = 0
second_max_diff = 0
for i in range(n):
for j in range(i+1, n):
if np.isinf(dist[i][j]) and not np.isinf(dist1[i][j]):
diff = dist1[i][j]
elif not np.isinf(dist[i][j]) and np.isinf(dist1[i][j]):
diff = dist[i][j] - 0
else:
diff = dist[i][j] - dist1[i][j]
diff_sum += diff
if diff > max_diff:
second_max_diff = max_diff
max_diff = diff
elif diff > second_max_diff:
second_max_diff = diff
return diff_sum, max_diff, second_max_diff
# 计算每种情况的最短距离差
diff_list = []
for A_new in A_list:
diff = calc_diff(A, A_new)
diff_list.append(diff)
# 找出最大和次大的最短距离差对应的添加线路
max_diff_idx = np.argmax([diff[1] for diff in diff_list])
second_max_diff_idx = np.argmax([diff[2] for diff in diff_list])
print("缩短距离最大的添加线路为:", A_list[max_diff_idx])
print("缩短距离第二大的添加线路为:", A_list[second_max_diff_idx])
```
代码中使用了 Floyd 算法计算最短距离,使用了 Numpy 库进行矩阵运算。计算每种情况的最短距离差后,通过 Numpy 库的 `argmax` 函数找出最大和次大的最短距离差对应的添加线路。
阅读全文