On a parametric shortest path problem from primal—dual multicommodity network optimization

Each iteration of the primal—dual linear programming algorithm entails a dual update. For the maximal multicommodity flow problem, and for multicommodity network synthesis, that requires finding a breakpoint in a parametric all pairs' shortest path problem. A procedure based on the Floyd—Warshall Algorithm solves this problem in polynomial (cubic in the number of nodes) time.