An efficient primal–dual algorithm for shortest path problem

There are numerous problems in combinatorial optimization. Their solutions are different from one another. There has not been found an unified approach that can be used for all problems in combinatorial optimization. However, there still exists a unified approach that can be used to solve a class of problems in combinatorial optimization relating to graphs; this approach is the primal–dual algorithm. In linear program, the authors solve the dual relaxed problem (DRP) to get an optimal solution V* first, and then endeavor to improve the feasible solution to D. But in combinatorial optimization, we need only a feasible solution &Vmacr; to DRP, and replacing V* by &Vmacr;, the authors carry on the relating calculation. Finally, it will be shown that the optimal solution can be obtained or P has no solution.