algorithm - KSPA on undirected graph的建议

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' 路径中最差的路径。