无向图上 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”边。显然，该算法具有组合复杂性，并且会在大型图上阻塞服务器。人们向我推荐了爱普斯坦的算法（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' 条路径中最差的路径进行比较。