This is the story of one of those times when Big-O complexity of an algorithm really really matters. The problem I was dealing with was to find equal-cost multiple paths in a data-center network. My initial approach was to use JGrapht library's KShortestPaths to find top K shortest paths and then iterate over them starting from least-cost path, to select all the paths with equal cost. This also allows to alter the definition of "equal-cost" by allowing some tolerance in costs to be considered equal .So far, so good. Until, I ran the algorithm on a medium-sized graph with ~400 nodes and ~1100 links. Who could have guessed that a single such calculation of shortest paths would take almost 3000 ms?! Well, you could have guessed it, had you noticed the Big-O complexity of JGrapht's KShortestPaths. It's O(k*n*(m^2)), where m is the number of edges (here, 1100) , n is the number of vertices (here, 405) and k is the number of paths. A simple rule of thumb to estimate if an algorithm is going to run in reasonable time (less than 1 second) is to see if the quantity mentioned in Big-O (here, k * n * m ^2) is less than 10 ^ 6. With JGrapht's KShortestPaths, it's more like 10^9 (16 * 400 * 1100 ^ 2, here k = 16), and therefore it was destined to take too long even on a medium-sized graph.
In comes, Yen's Algorithm to find top-k shortest loop-less paths (who wants a loop anyway!) and the execution time for one such calculation goes down from ~3000 ms to ~1 ms. I used the implementation given here, which although has a worst-case complexity of O(k*n(m + nlogn)), usually performs better than that as observed in computational experiments. For n = 400, m = 1100, the quantity inside Big-O is well below 10 ^ 6, and therefore performs much better as compared to JGrapht's KShortestPaths. In short, Yen's algorithm deserves to be in JGrapht for its sheer performance advantage.
In comes, Yen's Algorithm to find top-k shortest loop-less paths (who wants a loop anyway!) and the execution time for one such calculation goes down from ~3000 ms to ~1 ms. I used the implementation given here, which although has a worst-case complexity of O(k*n(m + nlogn)), usually performs better than that as observed in computational experiments. For n = 400, m = 1100, the quantity inside Big-O is well below 10 ^ 6, and therefore performs much better as compared to JGrapht's KShortestPaths. In short, Yen's algorithm deserves to be in JGrapht for its sheer performance advantage.
