Lesson 5.
2
4.4
Weighted Graphs
Learning Objective:
Find the length of the shortest path between
two vertices in a weighted graph using
Dijkstra’s Algorithm.
.
A weighted graph is a graph in which each edge is
associated with a value, called a weight.
Surigao 175
Tandag
Example : Shown in Figure 5.2.1 128
a weighted graph where the 210 140
number of kilometers (as weight)
between the corresponding cities.
Butuan 43
. 102 Bislig
Bayugan
.
.
Figure 5.2.1
.
.
One of the applications for weighted graphs is finding the shortest path
between two vertices.
. • Maps with weights representing distances
. • Water networks with weights representing water capacity of pipes
.
• Electrical circuits with weights representing resistance or maximum voltage
or maximum current
. • Computer or phone networks with weights representing length of wires
.
between nodes (vertices)
.
A path from a vertex u to a vertex v of a graph is a sequence of adjacent edges
starting u and ending in v such that the end of each edge other than the last one is the
start of the next edge in the sequence.
The length of a path is the sum of the weights of the edges of the path.
Example By inspection, there are five paths from A to F,
B 9 D namely,
ABCDF of length 32 (6+8+11+7)
6 7
11 ACEF of length 21
8
A F ACBDF of length 32
. 8 6 ABDF of length 22
.
C 7 E ACDF of length 26
.
. Thus, the shortest path from A to F is ACEF of
. length 21.
.
In the previous example, there are only five possibilities to consider, but in a more
complex graph, enumerating all paths would become impractical.
B 9 D
6 7
11
8
A F
8 6
C 7 E
five paths from A to F
ABCDF
ACEF
.
.
ABDF
. ACBDF
.
ACDF
.
.
One of the several algorithms that find the shortest path between vertices in connected
weighted graph is the one discovered by Dutch mathematician Edsger Wybe Dijkstra.
.
Dijkstra’s Algorithm
.
. Objective: This algorithm aims to find the shortest path from the start
.
vertex to every other vertex in a weighted graph.
.
.
Dijkstra’s Algorithm
Step 1 Label the start vertex with permanent label 0 and order label 1.
Step 2 Assign temporary labels to all the vertices that can be reached directly from
the start vertex.
Step 3 Select the vertex with the smallest temporary label and make its label
permanent. Add the correct order label.
Step 4 Put temporary labels on each vertex that can be reached directly from the vertex
you have just made permanent. The temporary label must be equal to the sum of the
permanent label and the direct distance from it. If there is an existing temporary label at
a vertex, it should be replaced only if the new sum is smaller.
.
Step 5 Repeat from Step 3 until the destination vertex has a permanent label.
.
.
Step 6 To find the shortest path, use the permanent labels to trace back from the end
. vertex to the start vertex. Write the route forwards and state the length.
.
.
Example 1
The network below give estimated times in minutes to travel along roads
joining some places in Caraga Region. Suppose you wish to use the quickest
route from Butuan to Tandag. Use Dijkstra’s algorithm to find the quickest
route (shortest path).
.
Order in which Distance from Butuan
vertices are labeled order Permanent label
to vertex
Temporary label
Step 1 Label the start vertex with
.
permanent label 0 and order label 1.
.
.
Order in which order Permanent label Distance from Butuan
vertices are labeled to vertex
Temporary label
Step 2 Assign temporary labels to all
the vertices that can be reached
directly from the start vertex.
.
order Permanent label
Temporary label
. Step 3 Select the vertex with the smallest
. temporary label and make its label
. permanent. Add the correct order label.
.
.
order Permanent label
Temporary label
Step 4 Put temporary labels on
each vertex that can be reached
directly from the vertex you have
just made permanent. The
temporary label must be equal to
the sum of the permanent label and
the direct distance from it. If there
is an existing temporary label at a
vertex, it should be replaced only if
the new sum is smaller.
.
order Permanent label
Temporary label
Step 5 Repeat from Step 3 until the
destination vertex has a permanent label.
Step 3 Select the vertex with the smallest
temporary label and make its label
permanent. Add the correct order label.
.
order Permanent label
Temporary label
(repeat of Step 3)
.
Order in which order Permanent label Distance from Butuan
vertices are labeled Temporary label to vertex
.
Order in which order Permanent label Distance from Butuan
vertices are labeled Temporary label to vertex
Step 6 To find the
shortest path, use the
permanent labels to trace
back from the end vertex
. to the start vertex. Write
. the route forwards and
. state the length.
.
.
Example 2 Find the shortest path from A to G using Dijktra’s Algorithm:
3 4
4 B 4 6 7
F
8 7
4 5
7 6 5 2
4 1 4
1 0 D
0 7 7
A
3 2 G
3 7 9
2 12 9 11
C 5 E
. 5 7
2 3
. 8 7
3
.
.
Shortest path/length : ABDEG of length 9
.
.
Thank you