Algorithms Unlocked by Thomas H. Cormen

Author:Thomas H. Cormen [Cormen, Thomas H.]
Language: eng
Format: epub, mobi, pdf
Tags: Algorithms, Computers, Programming
ISBN: 9780262518802
Google: r-oGPLclJc0C
Amazon: 0262518805
Publisher: MIT Press
Published: 2013-03-02T00:00:00+00:00

Chapter 6: Shortest Paths

111

0

1

0

3

8

1

B

B 1

0

1

1 C

@

C

1

4

0

1 A ;

2

1 5

0

which also gives the shortestŒu; v; 0 values7 (the weights of paths with

at most one edge). For example, shortestŒ2; 4; 0 is 1, because we can

get from vertex 2 to vertex 4 directly, with no intermediate vertices, by

taking edge .2; 4/ with weight 1. Similarly, shortestŒ4; 3; 0 is 5. Here

is a matrix giving the predŒu; v; 0 values:

0

1

NULL

1

1

NULL

B

B NULL NULL NULL

2

C

C

@ NULL

3

NULL

NULL A :

4

NULL

4

NULL

For example, predŒ2; 4; 0 is 2 because the predecessor of vertex 4 is

vertex 2, using the edge .2; 4/, with weight 1, and predŒ2; 3; 0 is NULL

because there is no edge .2; 3/.

After running the loop of step 3 for x D 1 (to examine paths that

may include vertex 1 as an intermediate vertex), the shortestŒu; v; 1

and predŒu; v; 1 values are

0

1

0

1

0

3

8

1

NULL

1

1

NULL

B

B 1 0 1

1 C

C

B

B NULL NULL NULL

2

C

C

@ 1 4

0

1 A and @ NULL

3

NULL

NULL A :

2

5

5

0

4

1

4

NULL

After the loop runs for x D 2, the shortestŒu; v; 2 and predŒu; v; 2

values are

0

1

0

1

0

3

8

4

NULL

1

1

2

B

B 1 0 1 1 C

B NULL NULL NULL

2

C

@

C

B

C

1 4

0

5 A and @ NULL

3

NULL

2

A :

2

5

5 0

4

1

4

NULL

After x D 3:

0

1

0

1

0

3

8

4

NULL

1

1

2

B

B 1

0

1

1 C

C

B

B NULL NULL NULL

2

C

C

@ 1

4

0

5 A and @ NULL

3

NULL

2

A :

2

1 5 0

4

3

4

NULL

7Because a three-dimensional array is a one-dimensional array of two-dimensional ar-

rays, for a fixed value of x we can think of shortestŒu; v; x as a two-dimensional array.

112

Chapter 6: Shortest Paths

And our final shortestŒu; v; 4 and predŒu; v; 4 values, after running the loop for x D 4, are

0

1

0

1

0

3

1 4

NULL

1

4

2

B

B 3

0

4 1 C

B 4

NULL

4

2

C

@

C

B

C

7

4

0

5 A and @

4

3

NULL

2

A :

2

1 5 0

4

3

4

NULL

We can see, for example, that the shortest path from vertex 1 to ver-

tex 3 has weight 1. This path goes from vertex 1 to vertex 2 to ver-

tex 4 to vertex 3, which we can see by tracing back: predŒ1; 3; 4 is 4,

predŒ1; 4; 4 is 2, and predŒ1; 2; 4 is 1.

I claimed that the Floyd-Warshall algorithm runs in ‚.n3/ time, and

it’s easy to see why. We have nested loops three deep, and each one

iterates n times. In each iteration of the loop of step 3, the loop of

step 3A iterates all n times. Likewise, in each iteration of the loop of

step 3A, the loop of step 3Ai iterates all n times. Since the outer loop

of step 3 also iterates n times, the innermost loop (step 3Ai) iterates n3

times in all. Each iteration of the innermost loop takes constant time,

and so the algorithm takes ‚.n3/ time.

It looks as though this algorithm also takes ‚.n3/ space in memory.

After all, it creates two n n .n C 1/ arrays. Since each array entry

uses a constant amount of memory, these arrays occupy ‚.n3/ mem-

ory space. It turns out, however, that we can get away with only ‚.n2/

space in memory. How? Just create shortest and pred as n n arrays, and forget about the third index into shortest and pred everywhere. Although steps 3Aia and 3Aib keep updating the same shortestŒu; v and

predŒu; v values, these arrays turn out to have the correct

Download

Copyright Disclaimer:
This site does not store any files on its server. We only index and link to content provided by other sites. Please contact the content providers to delete copyright contents if any and email us, we'll remove relevant links or contents immediately.