CODEWITHSUNDEEP
c#algorithmgraphpath
Schultz9999
Schultz9999

Reputation: 8946

Graphs: figure out if the path is at least X% better than others

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.

Upvotes: 1

Views: 173

Answers (1)

PengOne
PengOne

Reputation: 48398

The only way I see to do this is to remove the edges of the given path from the graph, find a minimum weight path from A to B in the smaller graph, and compare.

To solve this problem using this approach, try one of these well-studied algorithms:

  • Dijkstra's algorithm solves the single-source shortest path problems.
  • Bellman-Ford algorithm solves the single source problem if edge weights may be negative.
  • A* search algorithm solves for single pair shortest path using heuristics to try to speed up the search.
  • Floyd-Warshall algorithm solves all pairs shortest paths.
  • Johnson's algorithm solves all pairs shortest paths, and may be faster than Floyd-Warshall on sparse graphs.
  • Perturbation theory finds (at worst) the locally shortest path.

Upvotes: 2

Related Questions