Assume we have a path in an undirected cyclic weighted graph. Assuming we have an engine that can find a path from node A to node B in such a graph, is there an easy way/algorithm to figure out if the given path from A to B is at least X% better than any other disjoint path from A to B? By disjoint I mean two paths may not share any edges.
Graphs: the best path
1
$\begingroup$
algorithms
graph-theory
-
0@JosephMalkevitch: we already have A* based search e$n$gi$n$e. – 2011-10-10