含参数的最短路问题及其原始—对偶算法

The parametric shortest path problem with its primal-dual algorithm

对于含参数的网络图Gλ=(V ,E) ,本文用原始 -对偶算法求解Gλ 中自某一节点s到其它任意节点之间含参数的最短路 ,其时间复杂度为 0 (nm2 )。

Given a network G λ=(V,E) with a parameter λ, we use the Primal-Dual algorithm to solve the parametric shortest path problem from some vertex s to another in digraph G λ. And the algorithm run time of O(nm 2).