图解

伪代码

# 初始化
map = [[0, 3, INF, 7],
	   [8, 0, 2, INF],
	   [5, INF, 0, 1],
	   [2, INF, INF, 0]]
path = [[-1, -1, -1, -1],
		[-1, -1, -1, -1],
		[-1, -1, -1, -1],
		[-1, -1, -1, -1]]
		
for k in range(1, n+1):
	for i in range(1, n+1): 
		for j in range(1, n+1):
			if i == j:
				continue
			map[i][j] = min(map[i][j], map[i][k] + map[k][j])
			path[i][j] = k
# 最后得到的map就是最短路径，然后path就保存了信息，如何根据path来寻路呢？
# 其实也是一个思路，即path[i][j]是path[i][k]->path[k][j]，这样一层一层剥开直到终止条件-1