# 2. 算法描述

## 2.2 拓扑排序

1. 定义一个队列 Q，并把所有入度为 0 的节点加入序列。
2. 取队列首节点，输出。然后删去所有从它出发的边。并另这些边到达顶点的入度减 1，如
果某个顶点的入度减为 0，则将其加入队列。
3. 反复进行步骤 2，直到队列为空。

# 3. 实验代码

``````// An highlighted block
import copy
#拓扑排序
def topological_order(paths,indegree):
tempindegree = copy.deepcopy(indegree)
order = []
for i in range(len(tempindegree)):
if tempindegree[i] == 0:
order.append(i)
num = 1
finalorder = []
while len(order) != 0:
u = order.pop()
finalorder.append(u)
if num == len(tempindegree):
print("拓扑排序：",finalorder)
return finalorder

for j in range(len(paths)):
if paths[j][0] == u:
v = paths[j][1]
tempindegree[v] = tempindegree[v] - 1
if tempindegree[v] == 0:
order.append(v)
num = num + 1
#print(order)

if __name__ == "__main__":
paths = [
#用邻接表存储下这张表
[0,1,5],
[0,6,3],
[1,2,2],
[1,3,1],
[2,4,7],
[2,5,3],
[3,2,1],
[3,4,2],
[3,5,1],
[4,7,1],
[5,4,2],
[5,7,5],
[6,2,2] ]

#存储每个节点的入度
indegree = [0,1,2,1,3,2,1,2]
finalorder = topological_order(paths,indegree)
#每个节点当前的最短路径长度和上一跳的节点
length = [0,0,0,0,0,0,0,0]
lastnode = [-1,-1,-1,-1,-1,-1,-1,-1]
for i in finalorder:
for j in range(len(paths)):
if i == paths[j][1]:
if length[i] != 0 and length[i] < (length[paths[j][0]] + paths[j][2]):
continue
else:
#print("节点：",i,"path:",length[paths[j][0]],",", paths[j][2])
length[i] = length[paths[j][0]] + paths[j][2]
lastnode[i] = paths[j][0]
print("节点当前走过的最短路径",length)
print("上一跳节点",lastnode)
shortestpath = []
index = len(lastnode) - 1
while index != 0:
shortestpath.append(index)
index = lastnode[index]
shortestpath.append(0)
shortestpath.reverse()
print("最短路径的长度：",length[-1])
print("最短路径：",shortestpath)
``````

# 参考和致谢

[1]胡凡,曾磊.算法笔记[M].机械工业出版社:北京,2016.7:390-392.
[2]【MIT 课程】动态规划 I-最短路径算法 https://www.bilibili.com/video/BV1Y441157H7
[3]漫画：什么是动态规划？(整合版) https://www.sohu.com/a/149075950_684445

原文作者：zjutkarma
原文地址: https://blog.csdn.net/zjutkarma/article/details/117074380
本文转自网络文章，转载此文章仅为分享知识，如有侵权，请联系博主进行删除。