0
$\begingroup$

As I understand one can modify BFS for unweighted graph or Dijakstra for weighted graph to find all possible shortest paths from $s$ to $t$ in linear time. But how can this be, when there are $O(2^n)$ such paths? What am I missing here?

$\endgroup$
  • $\begingroup$ Why there are $2^n$ shortest paths? Between two nodes there is a path, totally there are $\frac{n(n-1)}{2}$ nodes, so the number of shortest paths is less than $n^2$. Am I missing something? Those algorithms also return one of the paths of there are many with the same weight. $\endgroup$ – Eugene Jun 1 '17 at 9:21
  • $\begingroup$ between two nodes there can be exponential number of paths on n clique for instance, you may "choose" the path from all the nodes so lets say fastest is k nodes , you will have the sum of n choose k as the number of paths with length k. $\endgroup$ – Dr.Haimovitz Jun 1 '17 at 9:24
  • $\begingroup$ see cs.stackexchange.com/questions/25842/… $\endgroup$ – Dr.Haimovitz Jun 1 '17 at 9:30
  • $\begingroup$ Okay, I think I see it. Shortest paths algorithms find the weight of the shortest path and the path with that weight between two nodes. The question of outputting all paths with that weight is different. $\endgroup$ – Eugene Jun 1 '17 at 9:42
  • $\begingroup$ @Eugene My answer gives a graph with about $2^d$ shortest paths between vertices at distance $d$. $\endgroup$ – David Richerby Jun 1 '17 at 10:16
2
$\begingroup$

As you (almost) observe, there can be $2^{\Theta(n)}$ shortest paths between a pair of vertices:

       *   *           *
      / \ / \ /     \ / \
    s*   *   *  ...  *   *t
      \ / \ /       / \ /
       *   *           *

With $k$ cycles, this graph has $3k+1$ vertices and there are $2^k = 2^{n/3-1}$ shortest $s$–$t$ paths: you can go clockwise or anticlockwise around each cycle, independently of the others.

The simple answer to your question is that you are mistaken. It is impossible for any algorithm to output all shortest paths in linear time (time $O(n)$), just because it is impossible to output an exponential amount of data in a polynomial number of steps: a Turing machine can only write one character of output per step.

Outputting all shortest paths is an example of an enumeration problem. Typically, we use different measures for these problems because it seems "unfair" to say that an algorithm is slow just because it has a lot of work to do. The usual standard for enumeration algorithms is to look at the number of steps between each successive output. Using modified Dijkstra will (I assume) have polynomial delay: there's a constant $c$ such that, for any large enough graph on $n$ vertices, the algorithm will output some shortest path after at most $n^c$ steps and, after each output, there will be at most $n^c$ more steps before the algorithm outputs another shortest path or terminates.

$\endgroup$
  • $\begingroup$ So as i understand the algorithms for this problem are just keeping truck on this paths but not outputing them, am i right? $\endgroup$ – Dr.Haimovitz Jun 1 '17 at 10:35
  • $\begingroup$ I'm not sure what you mean. The conventional algorithms for finding a single shortest path output as soon as they find one: they work in such a way that it's guaranteed that the first path that's found is a shortest one. Algorithms for outputting all paths generally output the paths one at a time, as they find them. $\endgroup$ – David Richerby Jun 1 '17 at 10:41
  • $\begingroup$ In modified Dijkstra if you keep all parents instead of just one in every relax step you save all the paths until current node and not just one, the algorithm is not outputing paths but saving them, when you print them you can find exponential number of paths though the modified Dijkstra take linear time as Dijkstra does $\endgroup$ – Dr.Haimovitz Jun 1 '17 at 10:52
  • $\begingroup$ @Dr.Haimovitz, yes, that's correct. You can generate a data structure that implicitly represents (keeps track of) all shortest paths, without actually generating all of them. $\endgroup$ – D.W. Jun 1 '17 at 15:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.