1
$\begingroup$

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.

  • 0
    When you mean cyclic, do you mean it's a cycle?2011-10-07
  • 0
    I mean it has cycles.2011-10-07
  • 0
    Perhaps this paper might be of use: http://dl.acm.org/citation.cfm?id=786362011-10-08
  • 0
    @JosephMalkevitch: we already have A* based search engine.2011-10-10

0 Answers 0