It is possible to find the shortest route thanks to algorithms like A*, bread first search, depth first search, etc..

Is there any known algorithm to find how many routes are available if there are more than 1 optimum solution (for example routes with same costs) or any solution at all.

I am working on some graph algorithms but I don't think I'm on the right direction. Any advices?

  • $\begingroup$ Check Dijkstra's algorithm, there's a modification to the standard algo that can give you all optimal paths. Also see stackoverflow.com/questions/2421605/… $\endgroup$
    – Naga
    Dec 13 '10 at 2:02
  • $\begingroup$ how about finding the amount of routes with a certain length? $\endgroup$
    – foobar
    Dec 13 '10 at 18:42
  • 1
    $\begingroup$ Bread first search certainly works, but possibly there are butter alternatives... $\endgroup$
    – Mike F
    May 8 '11 at 21:00
  • $\begingroup$ I don't see how Depth First Search helps in finding shorting routes. $\endgroup$
    – Srivatsan
    Aug 7 '11 at 6:41

I am guessing that determining the number of routes is undecidable because there may be an infinite number of optimal solutions (or there may be at least one optimal solution that is infinitely deep in the search tree).

With that said, there are simple ways to enumerate all optimal solutions.

If A* is used with an admissible and consistent heuristic, then A* is guaranteed expand nodes in non-decreasing order of path cost + heuristic cost (i.e., A*'s "$f$" function). Note that all optimal solutions will have the same $f$-cost. Therefore, to enumerate all optimal solutions, simply run A* until a goal-state is found (as usual). Then continue running A*, recording any additional goal-states it finds, until it expands a node with a higher $f$-cost (at which point we know that all of the optimal solutions have been found).

  • $\begingroup$ How can a graph have an infinite number of routes? If you are counting shortest paths / optimal solutions you are only considering simple paths and there are only a finite amount of simple paths, which clearly makes it decidable! $\endgroup$
    – sxd
    Jul 7 '11 at 20:47
  • $\begingroup$ @Dimitri: The question didn't say that the graphs were finite. (There are such things as graphs with infinite edges/vertices.) $\endgroup$
    – ESultanik
    Jul 7 '11 at 21:11

One way to represent a uniform-cost graph is with an adjacency matrix $A$ where $A_{i,j}$ is 1 if there is an edge from vertex $i$ to $j$ and 0 if there is not. ($A$ is symmetric for an undirected graph)

The integer matrix power $A^n$ has a neat property. $(A^n)_{i,j}$ counts the number of length-$n$ paths from vertex $i$ to vertex $j$. For $n=1$, you can see that this is the definition of the adjacency matrix.

If your edge costs are all integer weights (or just rational), then you can map that graph to a uniform-cost graph and preserve the optimal paths. You can then increase $n$ until $(A^n)_{i,j}$ is non-zero for the vertices of interest. That'll count the number of optimal paths.

I don't know the complexity analysis of this, but it doesn't sound too promising.


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.