Beyond the Void
BYVoid
次短路径与次小生成树问题的简单解法

[次短路径]

次短路径可以看作是k短路径问题的一种特殊情况,求k短路径有Yen算法等较为复杂的方法,对于次短路径,可以有更为简易的方法。下面介绍一种求两个顶点之间次短路径的解法。

我们要对一个有向赋权图(无向图每条边可以看作两条相反的有向边)的顶点S到T之间求次短路径,首先应求出S的单源最短路径。遍历有向图,标记出可以在最短路径上的边,加入集合K。然后枚举删除集合K中每条边,求从S到T的最短路径,记录每次求出的路径长度值,其最小值就是次短路径的长度。

在这里我们以为次短路径长度可以等于最短路径长度,如果想等,也可以看作是从S到T有不止一条最短路径。如果我们规定求从S到T大于最短路径长度的次短路径,则答案就是每次删边后大于原最短路径的S到T的最短路径长度的最小值。

用Dijkstra+堆求单源最短路径,则每次求最短路径时间复杂度为O(Nlog(N+M) + M),所以总的时间复杂度为O(NM*log(N+M) + M^2)。该估计是较为悲观的,因为一般来说,在最短路径上的边的条数要远远小于M,所以实际效果要比预想的好。

[次小生成树]

类比上述次短路径求法,很容易想到一个“枚举删除最小生成树上的每条边,再求最小生成树”的直观解法。如果用Prim+堆,每次最小生成树时间复杂度为O(Nlog(N+M) + M),枚举删除有O(N)条边,时间复杂度就是O(N^2log(N+M) + N*M),当图很稠密时,接近O(N^3)。这种方法简易直观,但我们有一个更简单,而且效率更高的O(N^2+M)的解法,下面介绍这种方法。

首先求出原图最小生成树,记录权值之和为MinST。枚举添加每条不在最小生成树上的边(u,v),加上以后一定会形成一个环。找到环上权值第二大的边(即除了(u,v)以外的权值最大的边),把它删掉,计算当前生成树的权值之和。取所有枚举修改的生成树权值之和的最小值,就是次小生成树。

具体实现时,更简单的方法是从每个节点i遍历整个最小生成树,定义F[j]为从i到j的路径上最大边的权值。遍历图求出F[j]的值,然后对于添加每条不在最小生成树中的边(i,j),新的生成树权值之和就是MinST + w(i,j) - F[j],记录其最小值,则为次小生成树。

该算法的时间复杂度为O(N^2 + M)。由于只用求一次最小生成树,可以用最简单的Prim,时间复杂度为O(N^2)。算法的瓶颈不在求最小生成树,而在O(N^2+M)的枚举加边修改,所以用更好的最小生成树算法是没有必要的。

[次短路径与次小生成树的例题]

HAOI 2005 路由选择问题 直接求次短路径。

pku 3255 Roadblocks 稍微特殊的次短路径,允许边重复走。

Ural 1416 Confidential 求次小生成树的问题、

pku 1679 The Unique MST 判断最小生成树是否唯一。

[参考资料]

BYVoid 原创讲解,转载请注明。


上次修改时间 2017-05-22

相关日志