Step 1: Compute the Bellman Value Function (BVF) (aka Distance transform) over your graph, with respect to the goal node. Call this V(x); the input argument 'x' is a vertex in your graph; V(x) returns the length of the shortest path from x to the goal (V(x) is easily computed over the whole graph at once in a breadth-first "wavefront-propagation" style -- easier than A*, actually).

Step 2: The length of the optimal path is given by V(start) (or U(end); they will be equal); from this calculate the threshold path length k=(1+p/100)*V(start) (paths with length greater than this you will not consider; paths with length less than this you want).

Step 3: Call f({start}, 0), where f(path_so_far, length_so_far) is defined,

function f(path_so_far, length_so_far){   PATHS = empty list;   if(path_so_far.end == goal)       Add path_so_far to PATHS and return PATHS.   for each vertex n in neighbors_of(path_so_far.end)       if(length_so_far + edge_cost(path_so_far.end, n) + V(n) < k)           Add all paths returned by,           f(path_so_far + n, length_so_far + edge_cost(path_so_far.end, n))           to PATHS.  // (Above, by "paths_so_far + n" I mean the                      //  path consisting of paths_so_far with the                      //  vertex n added to the end.)   return PATHS}

This will give you all of the paths you want.

Quote: Original post by Vorpy
There definitely exists an algorithm that will find the optimal path that is at least x% different than the optimal path if it exists for a general graph.

Just run a search on a graph where each node is a pair consisting of a node from the original graph and a counter that counts how many edges from the optimal path were taken to reach it. Nodes with a counter above a certain value simply don't exist in this new graph, and the edges can be easily mapped from the old graph to the new graph. The new graph is much bigger and so doing a search on it will take longer. Distance to goal from the original graph could be a good heuristic.

This will find an optimal solution but it probably won't be very fast.

I think that Vorpy's algorithm is close but not quite right, because you need to consider path costs from both sides. [Perhaps Vorpy had this in mind but had just left it out as an obvious implementation detail. In any event, it is included in the algorithm in my last post, which I think is correct.]

Quote: Original post by mfawcett
I've decided to simply store the optimal solution as I search, but instead of stopping the search once it's been found, continue searching and compare each solution to the optimal one, storing the ones that meet the threshold, and stopping the search once the requested number of routes have been found or once the search space is exhausted.

If this solves the problem to your satisfaction, awesome. But this does not give you all the paths within n% of optimal. It only gives you paths that visit a vertex only once, for starters.

Also, if all you want is the set of all nodes through which some path within n% of optimal passes (and not the paths themselves), then do,

1. Compute the Bellman Value Function (BVF) with respect to the goal node. Call it V(x).

2. Compute the BVF with respect to the start node. Call it U(x).

3. Any node s.t. U(x) + V(x) < k (where k is the threshold length described in my previous post) is inside this set; any other node is not. The meaning of U(x) + V(x) is that it is the length of the shortest path from 'start' to 'goal' passing through 'x'.

Emergent, thanks for replying! I thought the thread had died but it's nice to see renewed interest.

Quote: Original post by Emergent
If this solves the problem to your satisfaction, awesome. But this does not give you all the paths within n% of optimal. It only gives you paths that visit a vertex only once, for starters.

Aren't paths that visit the same vertex twice provably not optimal? I'm having a problem seeing how my solution doesn't give me the optimal solution, but maybe it's because I haven't defined the solution well enough and we are talking about solving different problems.

I'll take some time to digest the algorithm in your other post. It shouldn't be too hard since the Bellman-Ford Shortest Paths function is already implemented.

Quote: Original post by mfawcett
Aren't paths that visit the same vertex twice provably not optimal?

Let's say you want to get from a to d in the graph drawn below. The optimal path is (a, b, c, d), with cost 3 (assuming each edge costs 1). But you can also do (a, b, e, b, c, d) for a total cost of 5. So it's a path within n% of optimal for any n greater than or equal to ((5-3)/3)*100% ~= 67%. (I.e., if you request all paths within this percentage of optimal, your algorithm should include this one in the list of paths it returns). And obviously this path visits 'b' twice.

a --- b --- c --- d      |      |      e

So maybe we are talking about different problems?

Yes, poor wording on my part, I apologize. by "N% different" I really meant "only 100% - N% of the optimal path can be the same as this new path".

To be more precise, if you were to overlay a possible result and the optimal path, only 100% - N% of the optimal path can be co-linear for the result to be valid.

In your case, 100% of the optimal path would be co-linear with the next possible solution, so it can't be considered N% different.

I think you want to find A*, then do something like "cut out sections of the A* path and find A* path that relink at the two nodes you cut at. There may be lots of ways to cut the A* path, but you can make sure that you cut out at least 10% of the path to ensure you get a 10% difference. You'll want to consider only nodes that have 3 edges or more since you also wouldn't want your search for the sub-section replacement to touch any of the previous A* path.

This idea probably needs more work but I think may have potential since you're doing A* searches and only considering nodes on the A* path that have 3+ edges (which could be a ton).

Hope that helps.