Advanced High-School Mathematics

SECTION 2.2 Elementary Graph Theory 133

Step 1. Find the vertices v

in G such that (v 0 ,v) is a

directed edge. Temporarily

mark these vertices with their

weighted distrances fromv 0.

m^5 -

7

1 6

2

4 8

5

7 m

?

m

v 0

• m

m - m? - m?m

Step 2. Fill in the edge con-

necting v 0 to the vertex v of

minimal distance fromv 0 ; the

temporary label atv 1 is now

a permanent label.

m^5 -

7

1 6

2

4 8

5

7 m

?

m

v 0

• m

m - m? - m?m

Step 3. Find all new vertices

connected to v 1 ; temporarily

mark these vertices with their

distances fromv 0 throughv 1.

m^5 -

7

1 6

2

4 8

5

7 9

7

m?

m

v 0

• m

m - m? - m?m

Step 4. Select a vertexv 2 having

a minimal weight label; color

in the directed edge and make

the label permanent. (Note

that in the event that there is

more than one vertex of mini-

mal distance, the choice is ar-

bitrary.)

m^5 -

7

1 6

2

4 8

5

7 9

7

m?

m

v 0

• m

m - m? - m?m