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 的最短距离，（不能保证一直加最小数就是最短路径，可能中途遍历过程中就能找到最短路径了）