day 58 | 拓扑排序和 dijkstra
拓扑排序
- bfs
- 初始化，找到所有入度为 0 的节点加入 que
- 遍历 que， 每取出一个节点，就把他对应 start 边的 end 节点的入度度数-1
- 如果有对应度数为 0 的相邻点则加入 que
dijkstra 排序
- 维持一个点集合
- 往集合加入 1 节点，并且更新 mindist 数组（表示的是该节点到 1 的最短距离）
- 遍历所有节点，得到离当前结合最近的点 cur
- 更新和 cur 相邻的，且不在集合内的 mindist 距离
- mindist[i]=min(mindist[cur] + g[cur][i],mindist[i])
然后是关于是否可以有负数的问题
- Prime 维护的是一个 到集合的最短距离，所以可以有负数
- dijkstra维护的事节点到 start 的最短距离，（不能保证一直加最小数就是最短路径，可能中途遍历过程中就能找到最短路径了）
