TopKShortestPaths and Big-O Issues

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.