All possible paths in GetBestPath

[kungfu303]

In bidrectional_astar.cc, we have GetBestPath. If I want to see all of the possible paths that could have been traversed, is there a way to see or save those? This function, as the name says, gets the one singular best path, but can we save and see every less-than-optimal path from A to B?

[dnesbitt61]

No, once the best (least cost) path from A-B has been found the method exits. At any one edge, only the predecessor edge with least cost to the edge is stored, so there is no way to get less optimal paths (apart from the route alternates functionality).

[kungfu303]

Thanks @dnesbitt61, that makes sense. Could you explain more about the route alternates functionality?

[kevinkreiser]

yeah so the basic gist is this:

1. bidirectional a* maintains a forward search from the origin and a backward search from the destination
2. as the two search trees progress the algorithm checks if any of the trees ever see the same edge
3. if they do, that edge is a "connection" edge where the two trees connect and form a full path from origin to destination
4. every time we find a connection we remember where and what it costed
5. we search for a bit longer because our algorithms heuristic is not quite optimal (for the sake of performance)
6. if we find anything better in that extended search we replace the current best connection with that one
7. if alternates are enabled we may keep more of the connections that we find (if they are sufficiently different from previously found connections)

i believe your word choice is somewhat unfortunate and probably not what you meant. "all possible paths" doesn't make a whole lot of practical sense. i mean you can drive miami to get to portland maine from baltimore, but you shouldn't 😄

based on that assumption about what you're looking id say, like dave said, that alternates are probably what you really want. there is a configuration prameter that enables them for the service (a max number per request) and then there is a request parameter to tell the service you want some alternates returned.

note that this does not mean you'll always get alternates. sometimes the alternates are not different enough or too costly. the controls for those heuristics are in code at the moment.

[kungfu303]

@kevinkreiser, that makes a lot of sense. We were hoping to use alternates to debug paths that weren't what we would expect as the best path. We can configure some of these alternates to show with the param you all shared.

[dnesbitt61]

Check the api docs - there is an alternates request parameter that allows multiple routes to be returned. Others may add details on the implementation as I am not familiar with that code.

[gknisely]

#2626

[kungfu303]

Ah thank you both! @dnesbitt61 @gknisely