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?

  • 0
    I do$n$'t see how Depth First Search helps in finding shorting routes.2011-08-07

2 Answers 2

1

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

  • 0
    @Dimitri: The question didn't say that the graphs were finite. ([There are such things as graphs with infinite edges/vertices](http://mathworld.wolfram.com/InfiniteGraph.html).)2011-07-07
1

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.