5

有一个 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？

提前致谢，

4

1 回答 1

5

时间复杂度：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' 路径中最差的路径进行比较。
于 2009-08-25T08:50:05.123 回答