Suggestions for KSPA on undirected graph

Question

Hello Group,

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

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?

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

Thanks in advance,

Answer 1

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

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

We perform a modified Djikstra as follows:

• 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.