5
$\begingroup$

I have to generate all possible paths in a directed, acyclic weighted graph with edge costs. I also have to sort them in order of shortest path.

The simplest way that comes to mind is to do a depth-first search (DFS) for all paths, accumulating their edge costs as I traverse the paths, and then doing an NlogN sort on the result.

But I wondering if there is a better way to do this task. Are there any algorithms that could optimize this problem (combining DFS and a shortest path algorithm such as Dijkstra's maybe?).

Improve this question
$\endgroup$
13
  • 4
    $\begingroup$ Possibly Eppstein's k-th shortest path algorithm could be useful to you, you'd have to calculate the complexity though. However notice that a graph can have exponentially many paths, even between two vertices, so a polynomial (in the size of the graph) time algorithm is impossible. $\endgroup$
    – G. Bach
    Jan 16, 2014 at 2:19
  • 1
    $\begingroup$ Maybe to clarify: what is impossible in polytime is an algorithm that explicitly enumerates all paths sorted by length. What may possibly be possible is an algorithm that groups paths according to their length in sorted order and represents that grouping implicitly. $\endgroup$
    – G. Bach
    Jan 16, 2014 at 3:45
  • $\begingroup$ Thank you! This does correspond to the K shortest path routing problem. However, I wondering if I have a graph that is directed and acyclic (loop free) with a relatively small outdegree for each vertex (maximum 20 maybe...) and all possible paths have the same length is it still worth implementing Eppstein's algorithm, or is it better to use Dijkstra's algorithm generalized to find K shortest paths? $\endgroup$
    – Teresa
    Jan 16, 2014 at 17:21
  • $\begingroup$ "all possible paths have the same length". how can that be? that is an unusual graph type. what is it? is it even possible except on some kind of trivial graphs? suggest you focus on describing carefully (1) the nature of the graphs and (2) the result of the algorithm... there are many standard algorithms in this area, if more than one can work, then one can just compare their performance empirically... $\endgroup$
    – vzn
    Jan 16, 2014 at 19:52
  • 1
    $\begingroup$ If you really need only "few" shortest paths, Eppstein is probably the way to go (my remarks about real performance apply). I hope my answer sheds some light on the problem you originally asked; if there is something you want to ask about the k-shortest paths, feel free to open a new question. If there is more discussion to be had, please take it to chat. $\endgroup$
    – Raphael ♦
    Jan 17, 2014 at 21:49

1 Answer 1

Reset to default
6
$\begingroup$

The goal is to find all paths from $s$ to $t$ in a directed, acyclic graph with edge costs. Let $n$ the number of nodes, $m$ the number of edges and $p$ the number of $s$-$t$-paths. Let's look at what we have.

Naive enumeration

  1. Use any graph traversal from $s$ to find all paths.
  2. Sort them by length.

You can interleave the steps, but you'll end up with runtime $\Omega(n + p \log p)$ if there are $n$ nodes and $p$ paths.

Note that this algorithm is easy to parallelise.

Eppstein's Algorithm [1]

This one has runtime $O(m + n \log n + p)$ (from skimming the paper, I assume the bound is sharp, i.e. $\Theta$ holds). Note that paths are not represented explicitly.

I have no idea how well this algorithm can be parallelised.

Lower bounds

First of all, $p \in \Omega(2^n)$ in the worst case even in DAGs, see for instance this class of graphs:

enter image description here
[source]

Note that all nodes have small out-degree and all paths have the same length.

Therefore, $p$ dominates any algorithm for this problem (in the worst case) if we can not make further assumptions.

When you go for a traversal over all paths, you clearly have runtime $\Omega(p)$.

Conclusion

Eppstein's algorithm is asymptotically optimal even in the setting you describe. However, asymptotic analysis at this level is rough and hides "extra" work that may or may not pay off in practice (since $n$ does not tend to infinity). The naive version may very well be competitive in an application, depending on $n$, $m$ and $p$, and maybe even structural features.

Another thing to keep in mind is that above figures are all worst-case but you are probably after average runtime on some specific input set².

TCS papers are unlikely to contain a rigorous analysis that helps you decide (and it's hard to do, too). Your question reads as if your goal is a real-world application, so I recommend a pragmatic approach. If the naive approach is too slow for you, try parallelising it. If that is still to slow, you can invest the time, implement Eppstein and run some tests.

  1. Finding the k Shortest Paths by D. Eppstein (1998) [preprint]

  2. My group developed a method for semi-automated average-case analysis and a tool to perform it. Have a look, maybe it can help you find out more about performance on your data.

Improve this answer
$\endgroup$
2
  • $\begingroup$ This comment is late by a year and a half: isn't the number of paths in that graph in $\Omega(\sqrt{2}^n)$? $\endgroup$
    – G. Bach
    Aug 13, 2015 at 19:40
  • $\begingroup$ @G.Bach Right. I didn't explicitly state how many nodes there are, so let's say $2n+2$? ;D $\endgroup$
    – Raphael ♦
    Aug 14, 2015 at 0:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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