关于无向图的KSPA建议

Question

有一个KSPA的自定义实现需要重写.当前实现使用修改的Dijkstra算法,其伪代码在下面粗略地解释.它通常被称为KSPA使用边缘删除策略我认为如此.(我是图论的新手).

Step:-1.  Calculate the shortest path between any given pair of nodes using the Dijkstra algorithm. k = 0 here.
Step:-2.   Set k = 1
Step:-3.   Extract all the edges from all the ‘k-1’ shortest path trees. Add the same to a linked list Edge_List.
Step:-4.  Create a combination of ‘k’ edges from Edge_List to be deleted at once such that each edge belongs to a different SPT (Shortest Path Tree). This can be done by inspecting the ‘k’ value for each edge of the combination considered. The ‘k’ value has to be different for each of the edge of the chosen combination.
Step:-5.   Delete the combination of edges chosen in the above step temporarily from the graph in memory.
Step:-6.   Re-run Dijkstra for the same pair of nodes as in Step:-1.
Step:-7.   Add the resulting path into a temporary list of paths. Paths_List.
Step:-8.   Restore the deleted edges back into the graph.
Step:-9.   Go to Step:-4 to get another combination of edges for deletion until all unique combinations are exhausted. This is nothing but choosing ‘r’ edges at a time among ‘n’ edges => nCr.
Step:-10. The ‘k+1’ th shortest path is = Minimum(Paths_List).
Step:-11. k = k + 1 Go to Step:-3, until k < N.
Step:-12. STOP

据我理解算法,为了获得第k个最短路径,在每个源 - 目的地对之间找到"k-1"SPT,并且对于每个组合,每个来自一个SPT的"k-1"边缘将被同时删除.显然,该算法具有组合复杂性,并且在大图上阻塞服务器.人们向我推荐了Eppstein的算法(http://www.ics.uci.edu/~eppstein/pubs/Epp-SJC-98.pdf).但是这篇白皮书引用了一个'有向图',我没有看到它只适用于有向图.我只是想问一下这里是否有人在无向图上使用过这个算法？

如果没有,是否有良好的算法(在时间复杂度方面)在无向图上实现KSPA？

提前致谢,

Answer 1

时间复杂度:O(K*(E*log(K)+ V*log(V)))

存储器复杂度为O(K*V)(+ O(E),用于存储输入).

我们按如下方式执行修改后的Djikstra:

• 对于每个节点,而不是从起始节点保持当前已知的最佳路由成本.我们从起始节点保留最好的K路线
• 当更新节点的邻居时,我们不检查它是否改进了当前已知的最佳路径(就像Djikstra那样),我们检查它是否改善了K'当前已知的最佳路径.
• 在我们已经处理了节点的K个最佳路线中的第一个之后,我们不需要找到K个最佳路线,但只剩下K-1,并且在另一个K-2之后.这就是我所说的K'.
• 对于每个节点,我们将为K'当前已知的最佳路径长度保留两个优先级队列.
  • 在一个优先级队列中,最短路径位于顶部.我们使用此优先级队列来确定哪个K'最佳,并将在常规Djikstra的优先级队列中用作节点的代表.
  • 在另一个优先级队列中,最长路径位于顶部.我们使用这个来比较候选路径到最差的K'路径.