Trancy

最短路(我就不想码了

1.dijkstra 大概就是从节点出发,遍历它能到达的所有节点,并更新它的dis值,然后选取和它距离最短且【没有访问过的】节点,从那个节点开始重复下一轮的这些步骤,直至终点被访问到就结束。

这里的dis只能记录点到起点的距离

2.floyd 同DP的更新

3.SPFA可以处理负环 从起点放入队列。拿出队列的第一个元素开始,只要能更新dis值且不在队列,就把它加入队列。 函数结尾记得要消除标记。还是编一下吧。


评论