Why can Dijkstra's Algorithm be modified to find K shortest paths?

user_15662114 0
Viewed 411

I am trying to find an intuitive explanation as to why we can generalize Dijkstra's Algorithm to find the K shortest (simple) paths from a single source in a directed, weighted graph with no negative edges. According to Wikipedia, the pseudocode for the modified Dijkstra is as follows:

Definitions:
  G(V, E): weighted directed graph, with set of vertices V and set of directed edges E,
  w(u, v): cost of directed edge from node u to node v (costs are non-negative).
  Links that do not satisfy constraints on the shortest path are removed from the graph
  s: the source node
  t: the destination node
  K: the number of shortest paths to find
  P[u]: a path from s to u
  B: a heap data structure containing paths
  P: set of shortest paths from s to t
  count[u]: number of shortest paths found to node u

Algorithm:
  P = empty
  for all u in V:
    count[u] = 0
  insert path P[s] = {s} into B with cost 0

  while B is not empty:
    let P[u] be the shortest cost path in B with cost C
    remove P[u] from B
    count[u] = count[u] + 1
    
    if count[u] <= K then:
      for each vertex v adjacent to u:
        let P[v] be a new path with cost C + w(u, v) formed by concatenating edge (u, v) to path P[u]
        insert P[v] into B
  return P

I know that, for the original Dijkstra's Algorithm, one can prove by induction that when a node is added to the closed set (or popped from a heap if it's implemented in the form of BFS + heap), the cost to that node must be minimum from the source.

This algorithm here seems to be based on the fact that when a node is popped for the ith time from the heap, we have the ith smallest cost to it from the source. Why is this true?

shortest-path algorithm
1 Answers

The Wiki article doesn't specify, but that code will only solve the 'loopy' version of k-shortest-paths, where paths are not required to be simple.

The simple path version of the problem is harder: you'll want to look at something like Yen's algorithm, which does clever filtering to avoid repeated points when generating paths. Yen's algorithm can use Dijkstra's algorithm as a subroutine, but any other shortest-path algorithm can also be used instead.

There is no obvious way to modify Dijkstra's algorithm to solve the k-shortest-simple-paths problem. You'd need to track the paths in the priority queue (which is already done in your posted code), but there's an exponential upper bound on the number of times each vertex can be explored.

Here, if count[u] <= K puts an upper bound of K+1 on the number of times a vertex can be explored, which works for the non-simple path case. On the other hand, a direct modification of Dijkstra's algorithm for simple paths would, in the worst case, require you to explore a node once for each of the 2^(V-1) possibilities of which nodes had been previously visited (or possibly a slightly smaller exponential).

user_167571740
Related