两种次短路--最短路建模

2019-07-21

对于一个带权图，求两个顶点之间的次短路。次短路表示除最短路以外长度最小的路径。

实际上我们遇到的次短路问题分成两种，第一种次短路中可以重复经过一个点，第二种次短路不能重复经过一个点的。而这一个区别会导致解法上的很大区别。

对于第一种可以重复经过某个点的次短路，解法其实和求最短路相似，在进行 dijkstra 的过程中记录两个数组：dist0 和 dist1，分别表示最短路和次短路的答案。每次更新时需要依次判断是否可以更新次短路和最短路的值。由于需要计算次短路，所以调整后的 dijkstra 算法需要至少循环 2n−1 次才可以获得最终答案。
对于第二种不可以重复经过点的次短路，解法也比较直观简单，枚举两个顶点之间最短路上的每条边，每次在去掉这条边的剩下的图中计算最短路，取其中最小的一个答案就是最终次短路的答案。

比如下面这个图

1 - 3 的最短路为 1 -> 2 -> 3，长度为 2。

第一种次短路为 1 -> 2 -> 1 -> 2 -> 3，长度为 4。

第二种次短路为 1 -> 3，长度为 10。