代码随想录算法训练营第五十八天｜拓扑排序精讲，Dijkstra算法

拓扑排序

这个有向图转成线性的排序 就叫拓扑排序

当然拓扑排序也要检测这个有向图 是否有环，即存在循环依赖的情况，因为这种情况是不能做线性排序的。

所以拓扑排序也是图论中判断有向无环图的常用方法

可以用BFS& DFS两种方法解决

接下来我给出 拓扑排序的过程，其实就两步：

1. 找到入度为0 的节点，加入结果集
2. 将该节点从图中移除

Coding

1. 为了每次可以找到所有节点的入度信息，我们要在初始化的时候，就把每个节点的入度 和 每个节点的依赖关系做统计。

2. 用queue存放nodes whose in-degree = 0

3. 将该节点作为出发点所连接的节点的in-degree -1

Dijkstra朴素版

之前在optimization课堂上学过，希望作为复习，捡起来很快

求最短路

dijkstra算法：在有权图（权值非负数）中求从起点到其他节点的最短路径算法。

需要注意两点：

• dijkstra 算法可以同时求 起点到所有节点的最短路径
• 权值不能为负数

dijkstra三部曲：

1. 第一步，选源点到哪个节点近且该节点未被访问过
2. 第二步，该最近节点被标记访问过
3. 第三步，更新非访问节点到源点的距离（即更新minDist数组）