Study Bulletin AN EFFICIENT FOR SHORTEST P-D ALGORITHM PATH PROBLEM*
Shuli Liang · 1997
There are numerous problems in combinatorial optimization. Their solutions are different from one another. It has not been found an unified approach that can be used to all problems in combinatorial optimization. However, there still exists an unified approach that can be used to solve a class of problems in combinatorial optimization relating to graphs, this approach is primal-dual algorithm. (We simply call PD algorithm). In linear program, we solve DRP to get an optimal solution V* first, and then endeavor to improve the feasible solution to D. But in combinatorial optimization, we often only need a feasible solution V to DRP. And replacing V* by V, we carry on the relating calculation. Finally, it will show us that the optimal solution can be got or P has no solution. 1. PD Algorithm for Shortest Path Problem Shortest path problem is the most fundamental and also the most commonly encountered problem in the study of combinatorial optimization. It is a very active research field[ 11. Here we discuss how to use PD algorithm to find the shortest path from s to t. First we need an adequate linear programming formulation P and D, RP, DRP: P: min cx D: max wt - ws s.t. s.t. wj - wi _< c~j for each (i,j)