文档介绍：“An Efficient Algorithm for K Shortest Simple Paths”,算法思路清晰、叙述详实,借鉴了很多知名的K路径算法设计,具备很高的权威性。以下是对算法的译文介绍:
需要满足的前提条件如下:
应用于无向的图结构;
任意相连的两点的边权值大于0;
任意两点间的路径不允许成环,也就是路径中不包含重复节点;
4、无向图中的边的条数要大于等于节点的个数;
有关K路径算法的符号说明:
——无向图G
V ——包含n个节点的集合;
E ——包含m条边的集合;
——表示从指定节点s到t的第K优路径,那么就是s到t的最优路径,我们将采用
Dijkstra算法得出;
——图中节点v到所有其他节点的最短路径树;
——中v到u的最短路径;在无向图中始终满足,;
——经过的节点序列,用以表示;其中,;
——的初始部分,由个节点组成;
——的剩余部分,由个节点组成;此处,和均满足;
——当时,就等于(对于某个而言);但如果对于任何一个,当时,将从的某个点上偏离出去;后一种情况下,采用来表示节点,在该节点从中分支出去[也就是说,包含在当中,但不被包含];
——同样的,采用来表示节点,在该节点从的反向分支出去;
注1:对每一个在上的节点,均满足;
注2:在后续算法描述中,对任意节点均满足;
一、次优和渐次优路径算法描述
次优和渐次优路径算法描述及其所遵循的定理,是KSP算法的理论基础。现描述如下:
次优路径的计算
定理1
如果图中有若干条从s到t的不包含[也就是说,在到达之前从中偏离出去]的路径,那么其中必有一条相对最短的路径。这样的最短路径必然属于以下两种路径类型之一:
类型1:,且;
类型2:,此时既不在中,也不在中,且;
类型1和类型2的路径如下图所示,
类型1和类型2的路径图
类型1的最短路径可以通过穷举所有的节点获得;同样,类型2的最短路径可以通过穷举所有边获得;本算法中,将采用FSP子程序实现上述计算,FSP子程序将在后面介绍;
根据定理1,我们可以通过计算从s到t的不包含的最短路径的方式,获得。
渐次优路径的计算
为了计算,我们假设和共有一段初始子路径,但,满足。如果
是图中,从节点s到节点t的所有路径的集合,那么必将在中产生。在这里我们把分成以下的3部分:
……………………….(1)
………………………….. (2)
………………………………………………(3)
可以发现,如果,将是空集;如果,将是空集。从下图我们可以很明显的看出,各集合相互独立,它们的合集等于。此处,我们用
,和分别表示,,的最短路径,再在它们当中得出的最短路径就被认为是。
最短路径,和可以通过应用定理1按照如下的方式获得:
1、通过在中删除节点(连同它们之间的边),获得图。分别将节点和t作为起始和目标节点。在图中应用定理1获得路径P,其不包含
,那么。
2、通过在中删除节点和一条边,获得图。分别将节点和t作为起始和目标节点。在图中应用定理1获得路径P,其不包含,那么。
3、在图中应用定理1获得路径,其不包含。
二、优路径的系统产生
除了前面定义过的,,以外,以下给出了更多的需要用到的符号定义。
;………()
——索引值表示,对于,能够使与重合的最大值
;……………..()
——索引值表示,能够满足的最小值;能够保证和的公共部分是;
;………………..()
——用于存储的集合,以表明在节点,(并且满足)从中偏离出去;
;…()
——,用于存储节点的集合;
——从无向图中删除节点以及受它们影响的边以后,得到的图;
……………………………………………………………..()
……………………………………………()
——是图中,从节点s到节点t的所有路径的集合,并且假设成立;
——表示刨除前K-1条优选路径后的路径集合;算法中,将分成:
………….............()
(i)对于任意的均包含,但在到达之前从中分支出去(也就是说,不同于)。
(ii)如果,中的路径不会把作为它的初始子路径, [也就是说,不同于(满足)]。
各集合相互独立,它们的合集等于。属于每个非空集合的最短路径被存储在链表中,这样中的最短路径就是。以下描述了集合的系统化产生过程,以及每个集合中最短路径的计算过程。
对于(也就是说,已获得),存在路径集合。。很自然地,我们会考虑到这样的场景:内属于集合的最短路径成为,那么将被分成2 —