最短路与次短路的距离和计数
最短了距离:太多了不说了
次短路距离:
1)dijkstra
首先要明确一下次短路可以由那些值来更新,可以由前面已经确定的点的最短路和次短路更新
2)两次 dijkstra
①在不重复走一条路的前提下,把最短路的其中一段替换为另一段。
②找出最短路中的最短的一条边,重复走两次。(走过来又走回去).
两次dijkstra
4) spfa
这种和求最短路的方法相同,仅仅只是更改松弛时的操作,就相当于是求一个区间内的最大值和次大值一样,用两个数分别保存最大值和次大值,因此可以使用SPFA,并且只要松弛操作成功,就可入队。
spfa
最短路计数:
1) 方法
次短路计数:
首先在dijkstra中同时维护最短路拓扑树和次短路拓扑树 证只要明不存在值为0的环就一定也可以找到解,那么直接用djksstra做即可