Vol.13 No.2

ACTA M A T H E M A T I C A E A P P L I C A T A E SINICA

Apr., 1997

Study Bulletin

AN EFFICIENT P-D ALGORITHM FOR SHORTEST PATH PROBLEM* Y A N G CHENa'EN ( ~ , ~ - )

L I A N G SHULI ( ~ - )

(Department of Mathematics, Changsha Railway Ir~titute, Changsha 410075, China)

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 P D 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 p a t h 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: m a x wt - ws s.t.

s.t. wj - wi _< c~j for each ( i , j )

-Ax=

.t x _ > 0 fft

RP:

rain

~-'~x~

DRP:

max

vt-v8

k=l

s.t.

s.t. vj - vi _< 0, for each ( i , j ) E Q

-Ax+

=

Lz~'J x

> o,

x~>0,

:

1

= o,

k= l,... ,m

Received April 3, 1995. Revised July 15, 1996. * This research is supported by the National Natural Science Foundation of China under Grant 19271023.

222

ACTA M A T H E M A T I C A E A P P L I C A T A E SINICA

Vol.13

Note that the constraint equation A x -- (1, 0 , . . . , 0 , - 1 ) ~ has been multiplied by - 1 . For convenience, we define S -- { i : there exists a p a t h from s to i in graph D ( Q ) -- ( V , Q ) } , and define n-dimensional vector V as follows: vi =

-1, 0,

for i • S, otherwise.

(1)

It is not difficult to verify that V is a feasible solution to D R P (not necessary to verify V to be optimal) and Vb = 1 > 0 (when t-~S). T h e o r e m 1. The optimum of R P ( D R P ) is zero if and only if there exists a p a t h from s to ;t in D ( Q ) (i.e. t • S). Proof. Su1~ciency. If t • S, from (1) we have ~ = ~ = - 1 . This means t h a t the corresponding objective value is zero. Let s - p~ - P2 . . . . . p~ - t be the path from s to t, so for any feasible solution V to DRP we have vpl - vs <_ O, v ~ - vp, < O, . . . ,

vt - vp~ <_ O.

Adding two sides of all inequalities respectively, we obtain v~ - v8 <_ 0. Therefore V is optimal for D R / ' and the optimum is zero. Necessity. If the optimum of RP is zero, suppose that no path exists from s to t in D ( Q ) , i.e. t ~ S , then V, defined by (1), is a feasible solution to DRP, and the corresponding objective value is 1. This contradicts that the optimum of D R P is zero. Thus t E S. Let w be a feasible solution to D, we compute O: e

+

=

-

=

rain

{ c i j ~- w i -- ~ u j } -~ Cpq -J~ W p - - ~J)q > O.

(i,D~O, -V=~ >o Modifying w, we get w' (replace V* by V):

,

w,

=

f wi - 0, wl,

for i E S, for i-~S.

(2)

It is easy to verify w' is a new feasible solution to D, sets Q, S relating w' are denoted by Q', S' respectively. We have the following theorem. T h e o r e m 2. For w and w', we have IS[ < [S'[. Proof. If ( i , j ) 6 Q a n d i , j 6 s, then c~i + w Ii - w j I = c i j + w ~ - 8 - w j + 8 = 0. This implies that ( i , j ) • Q', i.e. S c S'. Define L = { j : i • S, j-~S, cij + w l - w j = 8}, if there exists a path from s to t in the graph, then L is not empty, i.e. ]LI > 0, suppose ! I Cqp'JffWp--Wq ~. 8, We have Cqp~J)p--Wq = Cqp-~Wp--9--'Wq ~- O, therefore (p,q) • Q', q • S t,

thus lSl < IS'I. From the above discussion, we develop the following P D algorithm for the shortest p a t h problem. (w.l.o.g. we assume ILl = 1) laD A l g o r i t h m . I n p u t : Digraph D = ( v , A ) , cii >_ 0 for each arc ( i , j ) • A vertices s and t. O u t p u t : Shortest path from s to t and its length. S t e p 1. Initialization k +- 0, w ° ~- 0 (i ----1, 2 , . . . , n), S +-- {s}. S t e p 2. Compute Qk =

rain_ {c j

{c j +

iEs, iEs W k+l ~

W ik _ 9 ~ ,

for i • S ,

w~,

for i'~S

if t • L ~ = { j : i • s, j ~ s ,

'

c~j + w~k - w~k__8~} go to Step 3.

Otherwise, k +- k + 1, S +- S U I k. Repeat Step 2.

No.2

EFFICIENT P-D ALGORITHM F O R SHORTEST PATH PROBLEM S t e p 3.

223

Stop. 2.

Analysis

and

Improvement

of PD

Algorithm

Because in Step 2 of PD algorithm, in order to compute 8k, ISI x (n - ISl) additions and (IS I × (n - I S ] ) - 1) comparisons are needed. In addition, IS] additions are necessary for computing w k+l, moreover Step 2 can be repeated (n - 1) times at most. Therefore the complexity of PD algorithm is O(n3). As Tarjan says: "the most efficient algorithm are generally those that compute exactly the information relevant to the problem situation"[2l. Therefore the total amount of computation can be decreased. First we need the following denotation and definition. For given S, we define: admissible path of S is a path consisting of the shortest path from S to i 6 S and arc ( i , j ) ( j ~ S ) , we use T(j) to denote the length of the shortest admissible path for given j, then T(j) = im~en{ d ( s , i ) + clj},

(3)

where d(s, i) is the shortest distance from s to i. We assume that

m i ~ {c,~ + , ~ } = %q + , %k

(4)

iEs,dEs

then m i l l {Cij -~ W i iEs, j-~s

.~- Cpq

-- ~1.18.

(5)

Since p, s E S, we have w pk - w sk = d(s,p) from Theorem 1, moreover for given S, Cnq+W pk - w sk is the least one of lengths of all admissible paths, therefore we have re_in {Tk(~)} = ~ a + ~ jEs

k

k

-- ~ 8 ,

clearly Ok = rain {Tk(j)} + Wsk .

(6)

des

To compute T(j) efficiently, obviously T0(j) = c~j (j # s). Assume that the value of T(j) in k-th iteration is Tk(j) ( j ~ S ) , then in (k + 1)-th iteration. S will contain a new vertex q, i.e. S I = S U {q}. It is easy to see: Tk+l(j) = rain {Tk(j), Tk(q) + Cqj}. jEs'

(7)

Therefore rain. {c~ + "~i

ifis', j'ffs'

Based on the above facts, the PD algorithm in Section 1 can be modified as follows: S t e p 1. Initialization k +-- O, w~0 +-- 0 (i = 1 , . . . , n), S +-- {s}, To(j) = c~j (j # s). S t e p 2. Compute ~ n {Tk(j)} = Tk(q),

k 0k = Tk(q) + ws,

w/k+1 =

"Wi - - Ok, for i E S, w~, for i-~S ' if q = t go to Step 3; else S = S U { q } ,

Tk+l(j) = mm {T~(j), Tk(j) + cqj}, jgs k +-- k + 1 repeat Step 2.

224

ACTA MATHEMATICAE APPLICATAE SINICA

Vo1.13

S t e p 3. Stop. In the modified PD algorithm, the c o m p u t a t i o n amount required in Step 2 in 2(n ISI) - 1 comparisons, (n - 1) additions, so the complexity of the modified PD algorithm is

3.

Conclusion

H o w to use primal-dual simplex algorithm to solve the shortest path problem, Papadimitriou and Steiglitzproposed firstsuch a primal-dual algorithm in their well-known book[ 4]. But the primal problem (P) used by them is different from ours in form. The P D algorithm proposed by them searches for shortest path from s to t backward from t, and our P D algorithm forward from s. It is just the same as Dijkstra's algorithm does. Nevertheless there exist some differences between our P D algorithm and Dijkstra's algorithm, that is, in Dijkstra's algorithm, if i G S, then its label becomes permanent, but in our P D algorithm for all vertices i 6 S the value of w~ will change in each iteration, in the meantime all value of wj for j-ES is identically equal to zero. A n d for i G S, wi - w s is the shortest distance from s to i. In the history of m a t h e m a t i c a l programming, K u h n invented the Hungarian algorithm which is the first polynomial-time algorithm in combinatorial optimization. Under the influence of K u h n ' s idea, later on Dantzig, Ford and Fulkerson developed the primal-dual simplex algorithm for linear p r o g r a m Is] . Now the primal-dual algorithms in turn are used to design polynomial time algorithm for some combinatorial optimization problems relevant to graphs. For instance shortest p a t h problem, m a x i m u m flow problem etc. [4'z] Solving some combinatorial optimization problems by using PD algorithm is still a very interesting research topic nowadays. References [1] R.K. Ahuja, T.L. Magnanti and J.B. Orlin. Network Flows. In G.L. Nemhauser, A.H.G. Rinnooy Kan and M.J. Todd ed.,Handbooks in OperationsResearch and Management Science,Vol.1, Optimization ElsevierSciencePublisherB.V., 1989, 211-369. [2] R.E. Tarjan. Data Structureand Algorithms. SIAM, Philadephia,PA, 1983. [3] E. Dijkstra. A Note on Two Problems in Connection with Graph. Numerische Mathematic, 1959, 1: 269-271. [4] C.H. Papadimitriou and K. Steiglitz. Combinatorial Optimization: Algorithms and Complexity. Printice-Hall, Englewood Cliff, NJ, 1982. [5] H.W. Kuhn. The Hungarian Method for the Assignment Problem. Nava/Res. Log. Quat., 1955, 2" 83-97. [6] G.B. Dantzig, L.R. Ford and D.R. Fulkerson. A Primal-Dual Algorithm for Linear Programs. In H.W. Kuhn and A.W. Tucker ed., Linear Inequalities and Related Systems, Annals of Mathematics Study, No. 38, Princeton University Press, Princeton, NJ, 1956, 171-181. [7] C.E. Yang and D.Y. Jin. A Primal-Dual Algorithm for the Minimum Average Weighted Length Circuit Problem. Networks, 1991, 21: 705-712.