Advanced High-School Mathematics

134 CHAPTER 2 Discrete Mathematics

Step 5. Find all new vertices

connected to v 2 ; mark these

with their distances from v 0

(along solid directed edges)

and throughv 2. If such a ver-

tex already has a temporary

label, overwrite this label if

the distance throughv 2 is less

than the existing label. (This

is where a label can change!

If there are no new vertices,

go to the next step.)

m^5 -

7

1 6

2

4 8

5

7 8

7

m?

m

v 0

• m

m - m? - m?m

Step 6 and beyond. Choose

the vertex having the minimal

temporary label. Color in the

directed edge and make the

label permanent. Keep re-

peating this process until all

vertices have permanent la-

bels; The darkened directed

edges determine a directed

tree through which minimal

weight paths are determined.

m^5 -

7

1 6

2

4 8

5

7 8

7

m?

m

v 0

• m

m - m? - m?m

m^5 -

7

1 6

2

4 8

5

7 8

7

m 14

?

m

v 0

• m

m?



?

m - -

Exercise.

1. Use Dijkstra’s algorithm to find a minimal-weight path from vertex
   Ato vertexJ in the graph on page 131.

2.2.4 Planar graphs

Two graphsG 1 andG 2 areisomorphic if there is a function

f: vertices ofG 1 −→ vertices ofG 2