建议KSPA在无向图 [英] Suggestions for KSPA on undirected graph

问题描述

有一个自定义实现KSPA的需要被重新写入。当前实现使用改进的Dijkstra算法，其伪code以下大致说明。它是采用边删除策略，我想是这样俗称KSPA。 （我是一个新手，在图的理论）。

There is a custom implementation of KSPA which needs to be re-written. The current implementation uses a modified Dijkstra's algorithm whose pseudocode is roughly explained below. It is commonly known as KSPA using edge-deletion strategy i think so. (i am a novice in graph-theory).

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是在每个源 - 目的地对和'k-1个'之间发现刃每个从一个SPT被同时对于每一组合中删除。 显然，这种算法组合的复杂性和木屐大图的服务器。人们建议我Eppstein的算法（<一href="http://www.ics.uci.edu/~eppstein/pubs/Epp-SJC-98.pdf">http://www.ics.uci.edu/~eppstein/pubs/Epp-SJC-98.pdf).但是，此白皮书列举了有向图和我没有看到提到它仅适用于有向图。我只是想问问人在这里如果有人用这种算法的无向图？

As i understand the algorithm, to get kth shortest path, ‘k-1’ SPTs are to be found between each source-destination pair and ‘k-1’ edges each from one SPT are to be deleted simultaneously for every combination. Clearly this algorithm has combinatorial complexity and clogs the server on large graphs. People suggested me Eppstein's algorithm (http://www.ics.uci.edu/~eppstein/pubs/Epp-SJC-98.pdf). But this white paper cites a 'digraph' and I did not see a mention that it works only for digraphs. I just wanted to ask folks here if anyone has used this algorithm on an undirected graph?

如果不是，是否有良好的算法（在时间复杂性方面）对一个无向图实施KSPA？

If not, are there good algorithms (in terms of time-complexity) to implement KSPA on an undirected graph?

在此先感谢，

推荐答案

时间复杂度：O（K *（E *日志（K）+ V *日志（V）））

Time complexity: O(K*(E*log(K)+V*log(V)))

（用于存储输入+ O（E））内存O（K * V）的复杂性。

Memory complexity of O(K*V) (+O(E) for storing the input).

我们进行修改Djikstra如下：

We perform a modified Djikstra as follows:

而不是从起始节点保持路线的最佳当前已知成本
• 对于每个节点，。我们保持最佳ķ路线从起始节点
• 当更新一个节点的邻居，我们不检查它是否改善了最佳当前已知路径（像Djikstra一样），我们判断是否提高了最坏的K'最好当前已知路径。
• 后，我们已经处理了第一个节点K最优路由，我们不需要得到k最好路由，但只有K-1个剩余，并且一个又一个的K-2。这就是我所谓的K'。
• 对于每一个节点，我们将保持两个优先队列为K'最好的目前已知的路径长度。
  • 在一个优先级队列中的最短路径之上。我们使用此优先级队列，以确定该K'的是最好的，在常规Djikstra的优先级队列作为节点的重新presentative将被使用。
  • 在其他优先队列中的最长路径是在顶部。我们用这个来比较候选路径最坏的K'路径。
  • For each node, instead of keeping the best currently-known cost of route from start-node. We keep the best K routes from start node
  • When updating a nodes' neighbours, we don't check if it improves the best currently known path (like Djikstra does), we check if it improves the worst of the K' best currently known path.
  • After we already processed the first of a nodes' K best routes, we don't need to find K best routes, but only have K-1 remaining, and after another one K-2. That's what I called K'.
  • For each node we will keep two priority queues for the K' best currently known path-lengths.
    • In one priority queue the shortest path is on top. We use this priority queue to determine which of the K' is best and will be used in the regular Djikstra's priority queues as the node's representative.
    • In the other priority queue the longest path is on top. We use this one to compare candidate paths to the worst of the K' paths.

    这篇关于建议KSPA在无向图的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！