- Email: [email protected]

Science,

The

University

of

Iowa,

Iowa

City,

ABSTRACT: In this paper we present an O((V( . loglV() algorithm forfinding an optimum path between two nodes in an edge-sparse network using a new approach. The method

exploits the data structure and a simple breadth-first search process.

I. Introduction

Let N = (V, E) be a network where V is a set of (VI nodes, E C {(u, v) )u, u E V, u 3 u] is a set of arcs and c,,,(O 5 c,,, 5 w) is the weight or capacity of the arc (u, Y). Let s and t be any two nodes in V. The problem we are interested in is to ship the maximum amount of commodity from s to t in N using a single path and to identify such a path. We assume an edge-sparse network N. The problem may arise in almost any practical network including computer and communication networks, as well as in transportation systems in reliability studies. In this paper, we provide an O() VJ * log (VI) solution to this problem and consider some of its variants. We use the standard terminology of graph theory (1). II. Optimum

Path Algorithm

Following Ford and Fulkerson (2) the residual flow of an s-t path in N becomes equal to the capacity of the minimum capacity arc in the s-t path. Thus, all that is needed is to generate all s-t paths and identify the one that has the maximum residual capacity amongst the set of these paths. However, the approach could be very inefficient computationally since the number .of such paths might grow exponentially in the general case. For example, for the complete graph with n nodes, by simple combinatoric arguments, one can see that there are exactly (n - 2)! s-t paths. One efficient approach is to use a variant of the shortest path algorithm, as indicated in (3). Another interesting possibility is to perform partial searches starting at vertex s using depth-fist search strategy (see (5) for depth-first search processes) which terminates when t is first reached in the appropriate 0

The

Franklin

Institute

0016-0032/82/110329-04$03.00/0

329

Kabekode

V. S. Bhat

subnetworks of N until an s-t path with the maximum residual capacity is identified. A stack S is needed. In the following we assume that there exists at least one path from s to t in N. We assume that the network N is connected. PUSH and POP are stack operations. TOP[S] is the element at the top of the stack. By N, - (u, u) we mean the network resulting from N, by deletion of the arc (u, u) from Nr. B and R are 1VI-vectors and bundle (a) denotes the set of arcs which have u as a vertex. The 1VI-vector P yields the optimum path from s to t in N, The following is our algorithm. Algorithm:

(OPT-PATH) N,: = N; R[s]: = large number;c: = 0; P[l]: = s; start: for i: = 1 step 1 until (VI do B[i]: = false;

search:

z: = 0; u: = s; if 3 (a, u) E N, such that B[u] = false then do begin if c,,, 2 c then do begin R[u]: = min[R[u], c,J, B[u]: = true; if u = t then do begin c: = R[t] for i = 1 step 1 until z do begin a: = TOP[S]

if c,, = c then N,: = N, - (u, u); P[z-i+l]:=u;POP; u: = u; end got0 start; end z: = z + 1; PUSH end

u; u: = u;

if c,,, < c then do N,: = N, - (u, u); goto search; end else if u r = s then do begin N,: = Nr-bundle(u), POP; u: = TOP[S], goto search end outputc,P[i]fori:=1,2 ,...,

z

end of OPT-PATH.

Next we claim the following. Theorem

The algorithm OPT-PATH works correctly and requires at most O(lEl*) time and memory, assuming list structure representation for the network. Proof: The algorithm clearly halts and yields a correct answer since it finds an s - t path that has maximum residual capacity amongst all possible sets of s - t paths. Journal

330

of the Franklin

Institute Ltd.

~ergamon Press

An Algorithm for Finding Optimum Path in Networks Each time an s-t path is found, at least one edge is removed from the network. For finding one s-t path, assuming list representation for the network, at most O((El) time is required from which we get the time bound as n 0(/E(‘). The memory requirements using list structure are O(lEj + ) VI). Next we consider an alternative approach. First, the set of arcs E is partitioned into the maximum number of blocks (denoted by k) so that arcs in the same block have the same capacity, whereas arcs belonging to different blocks have different capacities. Further, these blocks are ordered so that capacity of an arc in block Ci is greater than the capacity of an arc in block Ci-1, fori=2,3,4 ,..., k. Partitioning of the set of edges can be done by an efficient sorting algorithm (5) and will require 0(/E/ *log /El) time. Since the residual capacity of an optimum path must be equal to the capacity of some arc in N, one approach is to systematically identify such an arc for finding this value. This is achieved by the following. Algorithm 1: i: = 1, N,: = N. Step 1: N,: = NI - edges in C’i If 3 an s-t path in N, then do begin P: = the path found i:=i+l Goto step 1 end else output P end of algorithm 1. Clearly, the time complexity of the above algorithm for finding an optimum path is max[ O(lEl . log [El), O(k . [El)]. If k < log IEJ then the complexity is given by O((E( log (El). If k > log (El then the following approach can be taken. Consider the network N, defined by all edges in blocks C,, Cb+,, . . . , C, where b = [k/21. If N, has an s-t path then clearly optimum path exists in N, and optimum residual value is equal to or greater than the capacity of an arc in Cb. If N, has no s-t path then clearly optimum residual value is less than the capacity of an arc C,. In the former case delete the set of arcs in the blocks Ci, i=b,b+l; * . [(k - b/2)1 and obtain a new network N, and in the latter case includes all arcs from the blocks Ci, i = b - 1, * * * [(b - 1)/2] and let the resulting network be N1. N1 is again tested for the presence of an s-t path. The approach is similar to binary search and identifies a network N, defined by the arcs of the blocks {C,, Cb+,, * * *, CJ that has an optimum path for some b, but the network N2 defined by the arcs of the blocks (G+,, G+2, * . .T C,} does not have an s-t path. Clearly, in view of the one-to-one correspondence between the procedure and binary search, at most log2k major steps are required where in each of the steps, network construction and testing if an s-t path exists will require at most O(JE() by a depth-first search or breadth-first search process. Thus the time bound for this approach is clearly O(log k . (El). Using this approach, when k 2 log (El we Vol. 314. No. 5, pp. 3ZM32, Printed in Great Britain

November

1982

331

Kabekode

V. S. Bhat

have an O((El - log [El) algorithm for identifying an optimum s-t path in an arbitrary network. Since JEJ= O(l VI) f or edge-sparse networks, we have an O(l VJ * log [VI) algorithm. The method also finds the optimum cost as a byproduct. III. Conclusions

Given an edge-sparse network and two nodes s and t, we have presented an O(l VI - log I VI) method to identify a path that maximizes the flow from s to t. If while shipping maximum commodity from s to t we wish to ship maximum commodity from p to 4 in the network (using only one path), this can be achieved by our algorithm. All that is required is to apply the algorithm to a modified network consisting of all arcs of the original network which has residual capacity >O. Although the shortest path approach has also the same complexity as our algorithm, our method indeed is relevant as an alternative in the context of reliable computing. References

(1) F. Harary, “Graph Theory”, Addison-Wesley, Reading, Mass., 1%9. (2) L. R. Ford, Jr. and D. R. Fulkerson, “Flows in Networks”, Princeton University Press, Princeton, N.J., 1962. (3) P. Brucker, “R-Networke und matrixalgorithenen,” Computing, Vol. 10, pp. 281-283, 1972. (4) R. E. Tarjan, “Depth first search and linear graph algorithms”, Siam. J. Comput., Vol. 1, pp. 146160, 1972. (5) D. E. Knuth, “Sorting and Searching,” AddiFon-Wesley, Reading, Mass., 1973.

332

Journal

of the Frankh Institute Pemamon Press Ltd.