在某些应用中，需要计算两个节点之间的最短路径，比较有名的是Dijkstra算法和floyed算法，都是基于节点的邻接关系求解任意两点的可达性和最短可达路径。 Dijkstra算法比较容易理解，无论是广度优先还是深度优先都可以根据具体应用场景进行选择，不过，在计算较为复杂的场景中，比如节点数比较多，存在众多环路等情况，由于仅仅知道邻接关系，Dijkstra算法就显得力不从心，经常会在无关路径上浪费大量时间。相对而言，floyed算法应付此种场景就显得轻松很多。不过floyed 算法对计算有较高要求，算法复杂度为N的3次方，适合于节点间的关系不会经常变动的情况，提前将任意两点间的路径计算好，需要时直接使用即可。而Dijkstra算法属于轻量级的，对计算要求不高，在50-100个节点内进行还是实时查找也会比较轻松，反馈时间也比较快。

floyed  算法用程序实现极其简单，只需要对节点个数进行三个循环，在完成算法后，通过路径矩阵找到任意给定两点的最短路径，向floyed算法学习，路径的查找算法采用递归方式，尽量写的简洁。

def init_matrix(relations):
LEN = len(relations)
INF =  99999   

#初始化 距离矩阵和路径矩阵，默认所有位置都是INF
D  =  [[INF for x in range(LEN)] for y in range(LEN)]
P  =  [[y for x in range(LEN)] for y in range(LEN)]   

for line in relations:#对每个节点        
node = line[0]
neighbors = line[1]
if neighbors ==[]:            
continue
for nb in neighbors:
D[node][nb] = 1
P[node][nb] = -1

for line in range(LEN):
D[line][line] =0  
P[line][line] =0    

return (D,P)

def floyed_path(matrix):
DIST = matrix[0]
PATH = matrix[1]   
DIM = len(DIST)  
for loop1 in range(DIM):   
for loop2 in range(DIM):            
for loop3 in range(DIM):             
temp = DIST[loop2][loop1] + DIST[loop1][loop3]
if DIST[loop2][loop3] > temp:
DIST[loop2][loop3] = temp
PATH[loop2][loop3] = loop1                 
return (DIST,PATH)

def calc_shortpath(start,end,Path_Matrix):    
short_path =[]
mid_node = Path_Matrix[start][end]      
if mid_node == -1 or mid_node == start or mid_node == 0:  
return [start,end]
else:        
left_path = calc_shortpath(start,mid_node,Path_Matrix)        
right_path = calc_shortpath(mid_node,end,Path_Matrix)        
short_path = left_path[0:len(left_path)-1] + right_path        
return short_path

if __name__ == "__main__":   
mj_relation = [
[0,[1,3]],
[1,[2]],
[2,[4]],
[3,[4]],
[4,[5]],
[5,[6]],
[6,[7]],
[7,[3,8]],
[8,[]]
]

origin_matrix = init_matrix(mj_relation1)
result_matrix = floyed_path(origin_matrix)     

D = result_matrix[0]
P = result_matrix[1]
print(*D,sep="\n")   
print(*P,sep="\n")   
short_path  = calc_shortpath(0,8,P)   
print(*short_path,sep="  -->  ")