Dantzig G., Thapa M. Linear programming. Vol.1. Introduction

272 NETWORK FLOW THEORY

the set of successive augmenting paths the ones listed in the table. To see this note that

h

τ+2

= h

τ

− h

τ+1

and h<1.

 Exercise 9.14 Verify that Algorithm 9.1 can go through an inﬁnite number of iterations

as claimed in Example 9.10. Calculate, for each iteration 6τ + 1 through 6(τ +1)+1, ﬂows

on each arc and ﬂows into the origin 1 or out of the destination 8 as a function of τ and

show that these ﬂows are feasible.

 Exercise 9.15 Prove that the maximal ﬂow Algorithm 9.1 with the speciﬁed augment-

ing paths shown in Table 9-1 results in a ﬁnite total ﬂow of 1/h

2

.

 Exercise 9.16 Show that the result of Exercise 9.15 implies that for the purpose of

Example 9.10 the arcs that have inﬁnite upper bounds can be replaced by arcs that have

a bound of 1/h

2

.

 Exercise 9.17 Show that the maximal ﬂow through the network of Figure 9-13 is

inﬁnite.

BREADTH-FIRST UNBLOCKED SEARCH

A systematic procedure (which is a variation of the shortest path algorithm dis-

cussed in Section 9.5) for ﬁnding augmenting paths is the fanning-out (or breadth-

ﬁrst search) procedure. This requires forming a tree of all the nodes j that can be

reached from the source s by a ﬂow augmenting path. We ﬁrst illustrate this by an

example and then state the algorithm.

Example 9.11 (Illustration of the Breadth-First Unblocked Search) The steps

of the algorithm on the network displayed earlier in Figure 9-12 are displayed in Figure 9-

14. We begin with the starting set of nodes D

o

= {source node s} = {1}. Next take

the set of nodes j not in D

o

that can be reached from nodes i in D

o

by some arc (i, j)

that has positive remaining capacity in the adjusted capacity network. In Figure 9-14(a)

these nodes are 2 and 3. Denote this set by D

1

= {2, 3} and record the tracing-back

node of node 2 as 1 and of node 3 as 1 also. If D

1

contained the destination node 4 we

stop the forward search. Since this is not so we continue the forward search by looking

for nodes j not in D

o

or D

1

that can be reached from nodes i in D

1

by some arc (i, j)

that has positive remaining capacity in the adjusted capacity network. In Figure 9-14(a)

this is node 4. Denote this set by D

2

= {4} and record the tracing-back node of node 4

as 2. Since we have now reached the destination node 4, the θ-augmenting path (1, 2, 4)

is found by tracing back the path in reverse order (4, 2, 1) with arc capacities on (2, 4) of

1000 and on (1, 2) also of 1000 so that θ = min(1000, 1000) = 1000. After adjusting the

arc capacities along the path we obtain Figure 9-14(b).

On the next iteration of Algorithm 9.1 applied to Figure 9-14(b), we obtain D

0

= {1},

D

1

= {3} with the tracing-back node 1, and D

2

= {4} with the tracing back node 3

as shown in Figure 9-14(c). Since we have now reached the destination node 4, the θ-

augmenting path (1, 3, 4) is found by tracing back the path in reverse order (4, 3, 1) with arc

9.3 AUGMENTING PATH ALGORITHM FOR MAXIMAL FLOW 273

.

..

.

1

.

..

.

2

.

..

.

3

.

..

.

4

.

θ=1000θ=1000

....................................................

.

θ=1000

....................................................

.

θ=1000

.

1000

0 1000

0

(a)Iteration 1: Breadth-First Search

D

0

= {1},D

1

= {2, 3},D

2

= {4}

.

..

.

1

.

..

.

2

.

..

.

3

.

..

.

4

.

....................................................

.

....................................................

.

0

1000

1000 0

1

0 1000

0

1000

0

(b)Adjusted arc capacities

.

..

.

..

.

1

.

..

.

2

.

..

.

3

.

..

.

..

.

4

.

θ=1000θ=1000

....................................................

.

θ=1000

....................................................

.

θ=1000

.

1000

0 1000

0

(c)Iteration 2: Breadth-First Search

D

0

= {1},D

1

= {3},D

2

= {4}

.

..

.

..

.

1

.

..

.

2

.

..

.

3

.

..

.

..

.

4

.

....................................................

.

....................................................

.

0

1000 0

1

1000 0

0

1000

(d)Adjusted arc capacities

.

..

.

1

.

..

.

2

.

..

.

3

.

..

.

4

....................................................

.

θ=0

....................................................

.

θ=0

(e)Iteration 3: Breadth-First Search

D

0

= {1},D

1

= ∅

.

..

.

1

.

..

.

2

.

..

.

3

.

..

.

4

.

1000

0

10001000

1000

....................................................

.

F =2000

....................................................

.

2000

.

..

.

1000

0 1000

1

0 1000

0

(f) Maximal ﬂow

Figure 9-14: Augmenting Path Algorithm with Breadth-First Unblocked Search

274 NETWORK FLOW THEORY

capacities on (3, 4) of 1000 and on (1, 3) of also 1000 so that θ = min(1000, 1000) = 1000.

After adjusting the arc capacities along the path we obtain Figure 9-14(d).

On the next iteration of Algorithm 9.1 applied to Figure 9-14(d), the breadth-ﬁrst

unblocked search algorithm terminates with D

1

= ∅, implying that no additional ﬂow is

possible through the network, as shown in Figure 9-14(e). Either by adding the ﬂows in

Figure 9-14(a) and Figure 9-14(c), or better by comparing capacities in Figure 9-14(d) and

Figure 9-12, we obtain the maximal ﬂow of 2000, as shown in Figure 9-14(f).

Algorithm 9.2 (Breadth-First Unblocked Search) Let s be the source node, t be

the destination node, and let D

ν

be the boundary set of all nodes that can be reached

from s in exactly ν steps. The nodes in D

ν

are said to be a “distance” ν from s.

1. Set D

0

= {s} and ν =0.

2. Set ν ← ν +1.

3. If there exists a directed arc (i, j) along which additional ﬂow is possible (or if there

exists a directed arc (j, i) along which decreased ﬂow is possible) such that i ∈ D

ν−1

,

j ∈ D

h

, h =0, 1,...,ν − 1, set D

ν

to be the set of all such j, and mark each node

j ∈ D

ν

by recording its “predecessor” node i ∈ D

ν−1

, which we call its tracing-back

node. If no such arc (i, j) (or arc (j, i)) exists, set D

ν

to be the empty set.

4. If the ν-distance set D

ν

is empty, terminate with a statement that no augmenting

path exists.

5. If t ∈ D

ν

, terminate with a statement that an augmenting path exists and use the

tracing-back nodes (see Step 3) to generate an augmenting path from s to t.

6. Go to Step 2.

 Exercise 9.18 Prove that Algorithm 9.2 terminates with a shortest path in m(m−1)/2

comparisons.

THEOREM 9.11 (Edmonds-Karp Max-Flow Theorem) If a maximal ﬂow

exists, the augmenting path Algorithm 9.1, when used with the breadth-ﬁrst unblocked

search Algorithm 9.2 to ﬁnd the augmenting paths, will construct at most mn/2 path

ﬂows whose algebraic sum is the maximal ﬂow, where n is the number of arcs and m

is the number of nodes.

The key idea here is that at each iteration, the ﬂow augmenting path from the

source to the destination along which positive ﬂow is possible is chosen to be the

one with the fewest number of arcs.

 Exercise 9.19 Verify that Algorithm 9.1 with the breadth-ﬁrst unblocked search Algo-

rithm 9.2 takes no more than mn/2 iterations on the example in Figure 9-14.

 Exercise 9.20 Apply Algorithm 9.1 with the breadth-ﬁrst unblocked search Algo-

rithm 9.2 to the problem in Example 9.10 and show in this particular case that by selecting

at each iteration the augmenting path with the fewest number of arcs, Algorithm 9.1 ter-

minates in a ﬁnite number of iterations not exceeding mn/2.

9.4 CUTS IN A NETWORK 275

9.4 CUTS IN A NETWORK

The search for an augmenting path can be time-consuming, especially in large net-

works. Thus, it would be nice to be able to recognize optimality without doing an

exhaustive search for an augmenting path that may not exist. It turns out that it

is sometimes possible to prove that no such path exists by verifying that the con-

ditions of the Ford-Fulkerson max-ﬂow min-cut Theorem 9.13 are satisﬁed. These

conditions make use of the notion of a cut and its value.

Deﬁnition (Cut):Acut Q =(X,

¯

X) in a network is a partition of the node

set into two nonempty subsets X and its complement

¯

X = Nd \ X.IfX

contains the source node s and

¯

X contains the destination node t, the cut is

said to separate node s from node t.

Deﬁnition (Cut Value):If0≤ x

ij

≤ h

ij

for all (i, j) ∈Ac, then the cut value

C of a cut Q =(X,

¯

X) is the sum of the capacities of the arcs that start in

set X and end in set

¯

X; i.e.,

C =



i∈X



j∈Af (i)∩

¯

X

h

ij

, (9.14)

where Af (i)={j ∈Nd | (i, j) ∈Ac}. If each such arc (i, j) has a lower bound

l

ij

, not necessarily all zero, on the arc ﬂow x

ij

, then the cut value is

C =



i∈X



j∈Af (i)∩

¯

X

h

ij

−



j∈

¯

X



i∈Bf (j)∩X

l

ij

, (9.15)

where Af (i)={j ∈Nd | (i, j) ∈Ac} and Bf (j)={i ∈Nd | (i, j) ∈Ac}.

Deﬁnition (Saturated Arc): An arc is said to be saturated if it is used to full

capacity, i.e., x

ij

= h

ij

.

 Exercise 9.21 Given 0 ≤ x

ij

≤ h

ij

, show that if ﬂow F = F

o

> 0 is maximal, then

there exists at least one arc that is saturated. Construct a counter example if maximal

F = F

o

=0.

From Exercise 9.21 it follows that if the saturated arcs associated with a maximal

ﬂow are removed from the network by setting their capacities to zero, no ﬂow is

possible from the source to the destination over a path of remaining unsaturated

arcs, because if such ﬂow were possible, then the path would have positive arc

capacity for the adjusted capacity network formed, as discussed in Theorem 9.7, by

setting h



ij

= h

ij

− x

o

ij

, implying that the ﬂows x

ij

= x

o

ij

can be augmented along

the path. Then by Theorem 9.7 the ﬂows x

ij

= x

o

ij

would not be maximal.

276 NETWORK FLOW THEORY

.

..

.

1

.

..

.

2

.

..

.

3

.

..

.

4

.

2

1

2

3

....................................................

.

F =5

....................................................

.

F =5

.

..

.

4

2

02

1

03

2

0

.

(a)Max ﬂow value =5

Min cut value =5

.

..

.

1

.

..

.

2

.

..

.

3

.

..

.

4

.

2

1

2

3

....................................................

.

F =5

....................................................

.

F =5

.

4

2

02

1

03

2

0

.

(b)Max ﬂow value =5

Min cut value =5

Figure 9-15: Illustration of Min-Cut = Max-Flow

From the above discussion it is clear that the collection of saturated arcs in a

maximal solution can be used to deﬁne a partition of the nodes into two sets that

deﬁne a cut that separates the source from the destination.

Example 9.12 (Illustration of Min-Cut = Max-Flow) The network and ﬂows in

Figures 9-15(a) and 9-15(b) are identical to those in Figure 9-11(f). The saturated arcs in

Figure 9-15(a) are (1, 3), (2, 3), (2, 4), and (3, 4) with arc capacities (2, 1, 2, 3) respectively,

with total arc capacity of 8. Observe that there are many cuts in the network. In particular,

the cut Q =(X,

¯

X) with X = {1, 2} and

¯

X = {3, 4}, depicted by the use of a dotted line

that separates X and

¯

X in Figure 9-15(a), has a cut value of 5. Similarly, the cut depicted

in Figure 9-15(b), Q =(X,

¯

X) with X = {1, 2, 3} and

¯

X = {4} also has a cut value of 5.

The cut value 5 by accident happens to be the same in both cuts and also happens to be

the same value of that of the maximal ﬂow.

 Exercise 9.22 Find all other cuts in the network of Example 9-15. What is the rela-

tionship of the ﬂow value to the cut value of each of these cuts?

The relationship between ﬂow values and cut values is speciﬁed in Lemma 9.12

and Theorem 9.13.

LEMMA 9.12 (Flow Value Bounded by Cut Value) The ﬂow value F of

any feasible solution is less than or equal to the value C of any cut separating the

source s from the destination t.

THEOREM 9.13 (Ford-Fulkerson: Min-Cut = Max-Flow) The max-ﬂow

value is equal to the min-cut value.

 Exercise 9.23 (Duality) Show that the dual of the maximal ﬂow problem is the min

cut problem. Hint: Set up the maximal ﬂow problem as a linear program. Set up the dual

by letting u

j

be the multipliers corresponding to the nodes and let w

ij

be the multipliers

9.5 SHORTEST ROUTE 277

corresponding to the upper bounds on arc ﬂows, and show that the system is redundant.

The redundancy implies that we can set u

t

= 0, where t is the destination node; show

that this implies that u

s

= 1, where s is the source node. Next show that the remaining

variables are all either 0 or 1. Then show that for arc (i, j), we have w

ij

= 1 if and only

if u

i

= 1 and u

j

= 0. Use this last result to deﬁne the cut.

Example 9.13 (Another Example of Max-Flow) Consider the problem of ﬁnding

the maximal ﬂow in the network illustrated in Figure 9-16(a

1

). The capacities for each

direction of an arc are stated at the end of the arc where the ﬂow begins. Figure 9-

16(b

1

) represents a possible tree of positive arc capacities fanning out from the source.

The ﬂow can now be increased to θ

1

= 1 along the augmenting path (1, 2), (2, 4), (4, 6),

at which point the arcs (1, 2) and (2, 4) are saturated. The adjusted capacity network

is then constructed by adjusting the arc capacities to h



ij

= h

ij

− θ

1

and h



ji

= h

ji

− θ

1

along the augmenting path just considered. The resulting associated network is shown in

Figure 9-16(a

2

). In Figure 9-16(b

2

) is a new possible tree of positive arc capacities fanning

out from the source node 1, resulting in the path (1, 3), (3, 5), (5, 6). Arcs (3, 5) and (5, 6)

are saturated by assigning a ﬂow θ

2

= 1. The process is continued and the resulting path

and solutions are shown in Figures 9-16(a

3

), 9-16(b

3

), 9-16(a

4

), and 9-16(b

4

). Since it is

not possible to ﬁnd an augmenting path in Figure 9-16(b

4

), the process is terminated with

a maximal ﬂow of F

o

= θ

1

+ θ

2

+ θ

3

=3.

To ﬁnd the actual ﬂows on each arc we subtract the ﬁnal arc capacities in Figure 9-

16(a

4

) from the original arc capacities in Figure 9-16(a

1

), interpreting a negative diﬀerence

as a ﬂow in the opposite direction, to obtain the ﬁnal solution shown in Figure 9-17. To

ﬁnd the cut with minimum value, choose saturated arcs leading from nodes in X to nodes

in

¯

X. The nodes in X can all be reached from the source along unsaturated paths. This

set was determined by the nodes in the subtree of positive arc capacities in Figure 9-16(b

4

).

Hence X = {1, 3, 4, 2, 5} and

¯

X = {6} forms a cut Q =(X,

¯

X). The set of saturated arcs

joining the nodes in X to the nodes in

¯

X are (4, 6) and (5, 6), with sum of arc capacities

C

o

=2+1=3=F

o

, as shown in Figure 9-17.

 Exercise 9.24 In Figure 9-17 enumerate all the other cuts separating node 1 from

node 6. Show that their associated cut values are greater than the maximal ﬂow value.

9.5 SHORTEST ROUTE

The shortest route problem is that of ﬁnding the minimum total “distance”

along paths in an undirected connected network from the source s = 1 to the

destination t = m. The distance can be actual miles, the cost or time to go between

nodes, etc.

A simple method to solve such a problem for nonnegative distances (or costs) is

a branching out procedure that fans out from the source. Starting from the source,

it always picks on the next iteration the closest node i to the source and records its

distance. The algorithm is terminated when the shortest distance from the source

node to the destination node is recorded. We ﬁrst illustrate the algorithm and then

state it.

278 NETWORK FLOW THEORY

.

..

.

1

.

..

.

2

.

..

.

3

.

..

.

4

.

..

.

5

.

..

.

6

.

...........................................................................................

.

....................................................

.

Source

....................................................

.

Destination

1

3

0

1

0

1

2

1

0

(a

1

)

.

..

.

1

.

..

.

2

.

..

.

3

.

..

.

4

.

..

.

5

.

..

.

6

.

..

.

..

.

............................................................................................

.

............................................................................................

.

..

.

1

3

1

2

θ

1

=1

θ

1

=1

θ

1

=1

(b

1

)

.

..

.

1

.

..

.

2

.

..

.

3

.

..

.

4

.

..

.

5

.

..

.

6

.

...........................................................................................

.

0

3

1

0

1

2

1

0

(a

2

)

.

..

.

1

.

..

.

2

.

..

.

3

.

..

.

4

.

..

.

5

.

..

.

6

.

..

.

............................................................................................

.

..

.

..

.

3

1

θ

2

=1

θ

2

=1

θ

2

=1

(b

2

)

.

..

.

1

.

..

.

2

.

..

.

3

.

..

.

4

.

..

.

5

.

..

.

6

.

...........................................................................................

.

0

2

1

0

1

0

1

2

0

1

2

1

(a

3

)

.

..

.

1

.

..

.

2

.

..

.

3

.

..

.

4

.

..

.

5

.

..

.

6

.

..

.

..

.

2

1

θ

3

=1

θ

3

=1

θ

3

=1

θ

3

=1

θ

3

=1

(b

3

)

.

..

.

1

.

..

.

2

.

..

.

3

.

..

.

4

.

..

.

5

.

..

.

6

.

...........................................................................................

.

0

1

2

0

2

0

1

0

2

1

2

0

2

1

(a

4

)

.

..

.

1

.

..

.

2

.

..

.

3

.

..

.

4

.

..

.

5

.

..

.

6

.

..

.

............................................................................................

.

1

2

(b

4

)

Adjusted Arc Capacities

Search for Chain Flow

Figure 9-16: Another Example of the Max-Flow Algorithm

9.5 SHORTEST ROUTE 279

.

..

.

1

.

..

.

2

.

..

.

3

.

..

.

4

.

..

.

5

.

..

.

6

.

...........................................................................................

.

....................................................

.

3

....................................................

.

Max ﬂow F

o

=3

1

3

0

1

0

1

2

1

0

1

2

1

2

1

11

1

.

..

.

...............................................

.

...............................................

.

..

.

..

.

..

.

..

.

..

.

Min cut C

o

=3

Figure 9-17: Max-Flow Min-Cut Solution

Example 9.14 (Illustration of Dijkstra’s Algorithm) The steps of the algorithm

are illustrated in Figure 9-18. Let Nd = {1,...,6} be the set of nodes and Ac be the set

of arcs in the network. Let S be the set of nodes to which the shortest distances z

j

are

known at iteration k. We start by including the source node 1 in the set S, i.e., S = {1},

and assign it a distance label z

1

= 0 and a ﬁctitious predecessor node index p

1

= 0. Note

that z

j

is called a permanent label if j ∈S; this is shown by concentric circles in the ﬁgure.

Next we assign a temporary label z

j

= d

ij

to each node j ∈Nd \Sif an arc joins 1 to j

and z

j

= ∞ if no such arc exists. Thus

z

2

=3,z

3

= 8 and z

4

= ∞,z

5

= ∞,z

6

= ∞.

The corresponding predecessor indices are

p

2

=1,p

3

= 1 and p

4

=1,p

5

=1,p

6

=1

where we interpret p

4

= p

5

= p

6

= 1 as meaning that artiﬁcial arcs of inﬁnite length join

node 1 to nodes 4, 5, and 6 respectively.

On iteration 1 we start by picking the node with the smallest temporary label (with

ties broken randomly), i.e.,

k

∗

= argmin

j∈Nd\S

= argmin{z

2

,z

3

,z

4

,z

5

,z

6

} =2.

We now make node 2 a part of set S, i.e.,

S←S∪{2}

and call z

2

a permanent label. Next we update the temporary labels z

j

for j ∈Nd \Sif

there is an arc from the newly added node 2 to j. To do this deﬁne a set

Q = {j | (2,j) ∈Ac, for j ∈Nd \S}= {3, 4, 5}.

Then the temporary labels that need updating are for j ∈Q, and they are computed as

follows

z

j

← min{z

j

,z

2

+ d

2j

} for j ∈Q,

or

z

3

=5,z

4

=6,z

5

=4,

with predecessors

p

3

=2,p

4

=2,p

5

=2.

280 NETWORK FLOW THEORY

.

..

.

1

.

..

.

2

.

..

.

3

.

..

.

4

.

..

.

5

.

..

.

6

.

............................................................................................

.

............................................................................................

.

..

.

..

.

..

.

3

8

3

2

1

2

3

2

6

z

1

=0

p

1

=0

z

2

=3

p

2

=1

z

3

=8

p

3

=1

z

4

=∞

p

4

=1

z

5

=∞

p

5

=1

z

6

=∞

p

6

=1

Iteration 0: S = {1}

.

..

.

1

.

..

.

2

.

..

.

3

.

..

.

4

.

..

.

5

.

..

.

6

.

..

.

..

.

............................................................................................

.

............................................................................................

.

..

.

3

8

3

2

1

2

3

2

6

z

1

=0

p

1

=0

z

2

=3

p

2

=1

z

3

=5

p

3

=2

z

4

=6

p

4

=2

z

5

=4

p

5

=2

z

6

=∞

p

6

=1

Iteration 1: k

∗

=2,S = {1, 2}

.

..

.

1

.

..

.

2

.

..

.

3

.

..

.

4

.

..

.

5

.

..

.

6

.

..

.

..

.

............................................................................................

.

............................................................................................

.

..

.

..

.

..

.

3

8

3

2

1

2

3

2

6

z

1

=0

p

1

=0

z

2

=3

p

2

=1

z

3

=5

p

3

=2

z

4

=6

p

4

=2

z

5

=4

p

5

=2

z

6

=10

p

6

=5

Iteration 2: k

∗

=5,S = {1, 2, 5}

.

..

.

1

.

..

.

2

.

..

.

3

.

..

.

4

.

..

.

5

.

..

.

6

.

............................................................................................

.

............................................................................................

.

..

.

..

.

3

8

3

2

1

2

3

2

6

z

1

=0

p

1

=0

z

2

=3

p

2

=1

z

3

=5

p

3

=2

z

4

=6

p

4

=2

z

5

=4

p

5

=2

z

6

=10

p

6

=5

Iteration 3: k

∗

=3,S = {1, 2, 5, 3}

.

..

.

1

.

..

.

2

.

..

.

3

.

..

.

4

.

..

.

5

.

..

.

6

.

..

.

............................................................................................

.

............................................................................................

.

..

.

..

.

..

.

3

8

3

2

1

2

3

2

6

z

1

=0

p

1

=0

z

2

=3

p

2

=1

z

3

=5

p

3

=2

z

4

=6

p

4

=2

z

5

=4

p

5

=2

z

6

=9

p

6

=4

Iteration 4: k

∗

=4,S = {1, 2, 5, 3, 4}

.

..

.

1

.

..

.

2

.

..

.

3

.

..

.

4

.

..

.

5

.

..

.

6

.

..

.

............................................................................................

.

............................................................................................

.

..

.

..

.

..

.

..

.

3

8

3

2

1

2

3

2

6

z

1

=0

p

1

=0

z

2

=3

p

2

=1

z

3

=5

p

3

=2

z

4

=6

p

4

=2

z

5

=4

p

5

=2

z

6

=9

p

6

=4

Iteration 5: k

∗

=6,S = {1, 2, 5, 3, 4, 6}

Figure 9-18: Illustration of Dijkstra’s Shortest Route Algorithm

9.5 SHORTEST ROUTE 281

We continue with iteration 2 by picking the next node with the smallest temporary

label (with ties broken randomly), i.e.,

k

∗

= argmin

j∈Nd\S

= argmin{z

3

,z

4

,z

5

,z

6

} =5.

We now make node 5 a part of set S, i.e.,

S←S∪{5},

and call z

5

a permanent label. Next we update the temporary labels z

j

for j ∈Nd \S if

there is an arc from the newly added node 5 to j. To do this deﬁne a set

Q = {j | (5,j) ∈Ac, for j ∈Nd \S}= {6}.

Then the temporary labels that need updating are for j ∈Q, and they are computed as

follows

z

j

← min{z

j

,z

5

+ d

5j

} for j ∈Q,

or

z

6

=10,

with predecessors

p

6

=5.

The process then continues, as shown in the ﬁgure. Finally, on iteration 5 the shortest

distance is determined as z

6

= 9. It is straightforward to determine the shortest path

through the use of the predecessor nodes.

Algorithm 9.3 (Dijkstra’s Shortest Route Algorithm) Given a network G =

(Nd, Ac) with m>1 nodes, where s = 1 is the source node and t = m is the desti-

nation node. It is assumed that the distances between nodes are d

ij

≥ 0. On iteration τ ,

associated with each node j is (1) a distance z

j

from the source to node j along some

path P

j

, and (2) p

j

, which is the predecessor node to node j along the path P

j

. Also on

iteration τ, the nodes have been partitioned into two sets, S and Nd\S, where the paths P

j

leading to nodes j ∈Sare shortest paths. We will refer to z

j

as the label of node j.If

j ∈S, z

j

will be called its permanent label; otherwise it will be called its temporary label.

1. Start with the source node s = 1 as the initial set S of permanently labeled nodes;

i.e., S = {1}. Assign as its permanent label z

1

= 0, and predecessor p

1

=0. To

each of the nodes j ∈Nd \Sassign a temporary label z

j

equal to the distance on

an arc from the source to node j, and p

j

= 1; if no such arc exists, the label is

set to ∞ and p

j

= 1. Conceptually this implies that we are adding an artiﬁcial

arc from the source to every node that is not connected to the source with an arc.

Computationally we do not use ∞; instead we use a number greater than the sum

of the distances on all the arcs.

2. Set the iteration count: τ ← 1.

3. Find a node k

∗

∈Nd \Ssuch that

k

∗

= argmin

j∈Nd\S

z

j

and set S←S∪{k

∗

}.

Dantzig G., Thapa M. Linear programming. Vol.1. Introduction

Подождите немного. Документ загружается.