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.
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.
Here's how it works:
- Anybody can ask a question
- Anybody can answer
- The best answers are voted up and rise to the top