优化一 用队列每次的松弛过程中,我们不用对所有的边进行遍历,只需要对上一次松弛过后的能达到的点的集合进行遍历维护一个点集合, 每次松弛过后便把 to 节点加入到这个集合中。 每次松弛找的边都需要在这个点集合里面的点为开始既然是一个集合要避免重复加入变形二 判断负环判断 n-1 次必定能达到end,那么再判断一次,如果出现负环则路径会继续更行。变形二 判断 k 次至多经过 k 次城市可以达到的最短距离。 显然只需要松弛k+1次即可一个问题是松弛的过程中我们会对所有的边进行松弛,他们的先后顺序导致了我们松弛次数和实际经过节点个数的区别举个例子就是当边的先后顺序很好的时候一次遍历即可得到最短路径,但...