Over the weekend, I ran the Bellman Ford algorithm (All Pair Shortest Path). The algorithm has a running time of O(n2m). There were 20,000 nodes in the graph. And it was pretty dense or more inter-connected. The program ran for four hours with a CPU load of 100% on a quad-core processor.
I noticed a significant degradation in performance due to Page faults within the application.…