1.算法适用：
寻找给定的加权图中,网络上任意两点(node)间的最短路
2.算法步骤：
(1). 输入权矩阵(邻接矩阵)： D(0)?= D
(2). 计算：Dk?= (d(k)ij)n××n?(k = 1,2,3,...,n)
其中, d(k)ij?= min[d(k)ij, d(k-1)ik?+ d(k-1)kj].
(3). 输出最短路：Dn?= (d(n)ij)n××n?当 Dn?= Dn+1时迭代结束.d(n)ij为vi到vj的最短路长
3.python实现：
import numpy as np
import copy
def get_matrix(num_node):
#读取并生成邻接矩阵
m = np.zeros((num_node,num_node),dtype=float)
f = open('matrix_df.txt')
lines = f.readlines()
m_row = 0
for line in lines:
ls = line.strip('\n').split(' ')
m[m_row:]=ls[0:num_node]
m_row += 1
f.close()
p = np.array([[i] * num_node for i in range(num_node)])#初始化路径矩阵
return m,p
#递归函数 回溯中间点
def print_path(i, j):
if i == j:
#print(set_node.get(j+1),end='')
print(j+1,end='')
if i != j:
print_path(i, p[i][j])
#print('-->' + str(set_node.get(j+1)),end='')
print('-->' + str(j+1),end='')
#floyd
def floyd(num_node, start_node, end_node):
mat = copy.deepcopy(m)
for k in range(num_node):
for i in range(num_node):
for j in range(num_node):
if mat[i,k]+mat[k,j] < mat[i,j]:
mat[i,j] = mat[i,k]+mat[k,j]
p[i][j] = p[k][j]
#print("\nPath:({}-->{}):".format(set_node.get(start_node),set_node.get(end_node)),end='\n')
print("\nPath:({}-->{}):".format(start_node,end_node),end='\n')
print_path(start_node-1,end_node-1)
print('\nmin route:{}'.format(int(mat[start_node-1,end_node-1])))
return mat, p
if __name__ == '__main__':
#set_node = {1:'A',2:'B1',3:'B2',4:'B3',5:'C1',6:'C2',7:'D1',8:'D2',9:'D3',10:'E'} 当node不为数字时，用字典对应
num_node = eval(input("阶数:"))
m,p = get_matrix(num_node)
floyd(num_node,1,6)
?
4. 算例：
邻接矩阵：
[0 1 2 inf inf inf
inf 0 4 5 inf inf
inf 4 0 inf -3 inf
inf -2 2 0 2 inf
inf inf 4 2 0 1
inf inf inf 5 inf 0]
输出结果：
阶数: 6
Path:(1-->6):
1-->3-->5-->6
min route:0
|