Say you want to route two (or three, or four…) paths through a network between the same endpoints, and you want to make sure that they don’t overlap, so that if one path fails you can be pretty confident that the other paths are unaffected. The “naive” approach here might be to use Djikstra’s algorithm to find the shortest path through the network, then remove those links from the network and run it again to find the shortest path in the modified network.
This works sometimes but there are a bunch of cases where it can fail, because what you really need to do is find the shortest disjoint pair of paths. In this book, Dr. Ramesh Bhandari of AT&T describes many different techniques to find these paths. On the flight back from London I thought I’d try implementing his algorithm for shortest edge-disjoint pair routing. I didn’t quite get it done on one battery charge, but I’ve finished off a first attempt. The results are on GitHub, here.
Note: the unit test here shows a topology where the naive approach of running Djikstra twice will fail, but Bhandari’s algorithm will find the correct pair of paths.