Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
    
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/… –  Naga Dec 13 '10 at 2:02
    
how about finding the amount of routes with a certain length? –  foobar Dec 13 '10 at 18:42
    
Bread first search certainly works, but possibly there are butter alternatives... –  Mike F May 8 '11 at 21:00
    
I don't see how Depth First Search helps in finding shorting routes. –  Srivatsan Aug 7 '11 at 6:41
add comment

2 Answers 2

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

share|improve this answer
    
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! –  sxd Jul 7 '11 at 20:47
    
@Dimitri: The question didn't say that the graphs were finite. (There are such things as graphs with infinite edges/vertices.) –  ESultanik Jul 7 '11 at 21:11
add comment

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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