Calculating Divergent Paths on Subtending Rings
- by Russ
I need to calculate two paths from A to B in the following graph, with the constraint that the paths can't share any edges:
hmm, okay, can't post images, here's a link.
All edges have positive weights; for this example I think we can assume that they're equal. My naive approach is to use Djikstra's algorithm to calculate the first path, shown in the second graph in the above image.
Then I remove the edges from the graph and try to calculate the second path, which fails. Is there a variation of Djikstra, Bellman-Ford (or anything else) that will calculate the paths shown in the third diagram above? (Without special knowledge and removal of the subtending link, is what I mean)