Time Performance - mattrighetti/leiserson-retiming GitHub Wiki

WD

The WD algorithm is the most time consuming. The greater the number of nodes in the graph, the more time the algorithm will take to generate both W and D. This is due to the facts that the function for all-pairs shortest path finding by Floyd-Warshall takes the majority of time and has a big time complexity dependent on the number of nodes in the graph.

OPT1 vs OPT2

In this case OPT1 performs better than OPT2, that is because the Bellman-Ford algorithm that can be found in the NetworkX library is linked to a C++ library that makes it a lot faster than the Python implementation of OPT2 which introduces a noticeable overhead that reflects on worse time performance.