5
$\begingroup$

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?

$\endgroup$
4
  • $\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, 2010 at 2:02
  • $\begingroup$ how about finding the amount of routes with a certain length? $\endgroup$
    – foobar
    Dec 13, 2010 at 18:42
  • 1
    $\begingroup$ Bread first search certainly works, but possibly there are butter alternatives... $\endgroup$
    – Mike F
    May 8, 2011 at 21:00
  • $\begingroup$ I don't see how Depth First Search helps in finding shorting routes. $\endgroup$
    – Srivatsan
    Aug 7, 2011 at 6:41

2 Answers 2

Reset to default
1
$\begingroup$

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

$\endgroup$
2
  • $\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, 2011 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, 2011 at 21:11
1
$\begingroup$

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.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .