K Shortest Paths算法之Eppstein algorithm

Eppstein的算法是David Eppstein于1998年提出的一种高效且易于实现的k条最短路径寻找方法。它的时间复杂度为O(m + n log n + k)其中m是边的数量n是节点的数量k是要寻找的路径数。相较于其他方法它具有较好的性能和实用性。

Eppstein algorithm的关键步骤

1.对于给定的图G(V, E)构造所有节点到目标节点D的最短路径树。

2.初始化一个优先级队列Q将源节点S到目标节点D的最短路径P1放入队列Q。

3.对于每一条边(u, v)计算其对应的sidetrack边(u, v)。这里sidetrack边(u, v)表示使用边(u, v)替换从u到目标节点D的路径上的某个边所带来的权重变化。delta(u, v) = w(u, v) - w(T(u)) + w(T(v))其中w(u, v)表示边(u, v)的权重w(T(u))表示从u到目标节点D在最短路径P1中的路径的权重w(T(v))表示从v到目标节点D在最短路径P1中的路径的权重。

4.重复以下步骤K-1次以找到K条最短路径

• 从优先级队列Q中取出权重最小的路径P。
• 将路径P加入到最短路径列表中。
• 对于路径P上的每个顶点v找到sidetrack边(u, v)并计算新路径。将从源节点S到顶点u的路径P(u)与边(u,v)以及从顶点v到目标节点D的路径P’(v)连接起来形成一条新路径P’。将新路径P’加入到优先级队列Q中。

5.返回找到的K条最短路径。

Eppstein algorithm图例

1和2.构造所有节点到目标节点D的最短路径树并将源节点S到目标节点D的最短路径P1放入队列Q我这里两步并为一步了

3.假设图示的两个节点为u和v 计算sidetrack边(u, v)所带来的权重变化
deltauv= wuv-WTuWTv= 6 - 10 + 8 = 4

所谓的权重变化就是如果流量往sidetrack边(u, v)走的话整条路径的权重变化

接着我们计算所有sidetrack边的权重变化值将链路的weight改为权重变化值如下图所示注意处在最小路径树上的边权重变化为0

这样就计算出来第二段的路径A1=13+1=14如下图如果K=2的话那结果就是P1和A1
如果K>2的话将A1加入到Q队列后A1也成为最短路径树的一部分此时的sidetrack边(u, v)变成除了P1和A1以外的边再次重新计算所有sidetrack边(u, v)所带来的权重变化可能会变化并通过计算得到A2等

总体体验下来Eppstein的算法确实较于Yen的算法改进了不少尤其是时间复杂度方面而且算法本身也更加灵活

参考网站

Eppstein, David. “Finding the k shortest paths.” SIAM Journal on computing 28.2 (1998): 652-673.

https://epubs.siam.org/doi/pdf/10.1137/S0097539795290477?casa_token=O8yItNx7k4wAAAAA:wetCzycvyFhloRiOQU1M_W2S6cKzAb9kLWF06Lbx-OmqIb-MY9elNWN6H8E3whjK7Str-oDsdzQj