Network simplex algorithm

In mathematical optimization, the network simplex algorithm is a graph theoretic specialization of the simplex algorithm. The algorithm is usually formulated in terms of a standard problem, minimum-cost flow problem and can be efficiently solved in polynomial time. The network simplex method works very well in practice, typically 200 to 300 times faster than the simplex method applied to general linear program of same dimensions.

For a long time, the existence of a provably efficient network simplex algorithm was one of the major open problems in complexity theory, even though efficient in practice versions were available. In 1995 Orlin provided the first polynomial algorithm with runtime of ${\displaystyle O(V^{2}E\log(VC))}$ where ${\displaystyle C}$ is maximum cost of any edges. Later Tarjan improved this to ${\displaystyle O(VE\log V\log(VC))}$ using dynamic trees in 1997. Strongly polynomial dual network simplex algorithms for the same problem, but with a higher dependence on the numbers of edges and vertices in the graph, have been known for longer.

...
Wikipedia