Question

5. Apply Dijkstra's algorithm as discussed in class to solve the single-source shortest-paths problem for the following graph. Consider node A to be the source. (20 points) a. Show the completed table. b. State the shortest path from A to E and state its length. C. State the shortest path from A to F and state its length. d. State the shortest path from A to G and state its length. A 12 9 B 17 8 7 10 8 2 4 E TI 5

Answer 1

5.

a.

The source vertex is A.

The Dijkstra algorithm is applied as follows :

Initialization : Let d[v] represent the initial distance which is the shortest from source vertex A. So, initially, d[v] = ∞ for all vertices other than A and d[A] is initially 0.

Initialize a queue that will contain all the vertices along with their distances.

The queue is :

Vertex	A	B	C	D	E	F	G
Distance	0	∞	∞	∞	∞	∞	∞

Initialize an empty set S.

Step 1 :

• Remove the vertex from the which has minimum distance value.
• The vertex removed is A.
• Include the removed vertex into the set S as S = { A }.

Perform relaxation on the edges adjacent to vertex A.

For the edge AB,

d[B] > d[A] + wt[AB] is True.

d[B] = d[A] + wt[AB] = 0 + 12 = 12.

For the edge AC,

d[C] > d[A] + wt[AC] is True.

d[C] = d[A] + wt[AC] = 0 + 9 = 9

For the edge AD,

d[D] > d[A] + wt[AD] is True.

d[D] = d[A] + wt[AD] = 0 + 17 = 17

The queue is updated as :

Vertex		B	C	D	E	F	G
Distance		12	9	17	∞	∞	∞

The table for the algorithm becomes :

Node	Initial Distance	Distance	Predecessor
A	0	0
B	∞	12	A
C	∞	9	A
D	∞	17	A
E	∞	∞
F	∞	∞
G	∞	∞

Step 2 :

• Remove the vertex from the which has minimum distance value.
• The vertex removed is C.
• Include the removed vertex into the set S as S = { A, C }.

Perform relaxation on the edges adjacent to vertex C.

For the edge CD,

d[D] > d[C] + wt[CD] is True.

d[D] = d[C] + wt[CD] = 9 + 7 = 16

For the edge CF,

d[F] > d[C] + wt[CF] is True.

d[F] = d[C] + wt[CF] = 9 + 8 = 17

The queue is updated as :

Vertex		B		D	E	F	G
Distance		12		16	∞	17	∞

The table for the algorithm becomes :

Node	Initial Distance	Distance	Predecessor
A	0	0
B	∞	12	A
C	∞	9	A
D	∞	16	C
E	∞	∞
F	∞	17	C
G	∞	∞

Step 3 :

• Remove the vertex from the which has minimum distance value.
• The vertex removed is B.
• Include the removed vertex into the set S as S = { A, B, C }.

Perform relaxation on the edges adjacent to vertex B.

For the edge BD,

d[D] > d[B] + wt[BD] is False.

d[D] = 16

For the edge BE,

d[E] > d[B] + wt[BE] is True.

d[E] = d[B] + wt[BE] = 12 + 10 = 22

The queue is updated as :

Vertex				D	E	F	G
Distance				16	22	17	∞

The table for the algorithm becomes :

Node	Initial Distance	Distance	Predecessor
A	0	0
B	∞	12	A
C	∞	9	A
D	∞	16	C
E	∞	22	B
F	∞	17	C
G	∞	∞

Step 4 :

• Remove the vertex from the which has minimum distance value.
• The vertex removed is D.
• Include the removed vertex into the set S as S = { A, B, C, D }.

Perform relaxation on the edges adjacent to vertex D.

For the edge DE,

d[E] > d[D] + wt[DE] is True.

d[E] = d[D] + wt[DE] = 16 + 2 = 18

For the edge DF,

d[F] > d[D] + wt[DF] is False.

d[F] = 17

The queue is updated as :

Vertex					E	F	G
Distance					18	17	∞

The table for the algorithm becomes :

Node	Initial Distance	Distance	Predecessor
A	0	0
B	∞	12	A
C	∞	9	A
D	∞	16	C
E	∞	18	D
F	∞	17	C
G	∞	∞

Step 5 :

• Remove the vertex from the which has minimum distance value.
• The vertex removed is F.
• Include the removed vertex into the set S as S = { A, B, C, D, F }.

Perform relaxation on the edges adjacent to vertex F.

For the edge FG,

d[G] > d[F] + wt[FG] is True.

d[G] = 17 + 3 = 20.

The queue is updated as :

Vertex					E		G
Distance					18		20

The table for the algorithm becomes :

Node	Initial Distance	Distance	Predecessor
A	0	0
B	∞	12	A
C	∞	9	A
D	∞	16	C
E	∞	18	D
F	∞	17	C
G	∞	20	F

Step 6 :

• Remove the vertex from the which has minimum distance value.
• The vertex removed is E.
• Include the removed vertex into the set S as S = { A, B, C, D, E, F }.

Perform relaxation on the edges adjacent to vertex E.

For the edge EG,

d[G] > d[E] + wt[EG] is False.

d[G] = 20

The queue is updated as :

Vertex							G
Distance							20

The table for the algorithm becomes :

Node	Initial Distance	Distance	Predecessor
A	0	0
B	∞	12	A
C	∞	9	A
D	∞	16	C
E	∞	18	D
F	∞	17	C
G	∞	20	F

Step 7 :

• Remove the vertex from the which has minimum distance value.
• The vertex removed is G.
• Include the removed vertex into the set S as S = { A, B, C, D, E, F, G }.

But vertex G has no such adjacent edges such that the the other vertex is unvisited.

The queue is updated as :

Vertex
Distance

The table for the algorithm becomes :

Node	Initial Distance	Distance	Predecessor
A	0	0
B	∞	12	A
C	∞	9	A
D	∞	16	C
E	∞	18	D
F	∞	17	C
G	∞	20	F

So, the final completed table for the single source shortest path algorithm using Dijkstra algorithm is :

Node	Initial Distance	Distance	Predecessor
A	0	0
B	∞	12	A
C	∞	9	A
D	∞	16	C
E	∞	18	D
F	∞	17	C
G	∞	20	F

b.

The shortest path from A to E is :

A ------> C ---------> D ----------> E

The length of the path is 18.

c.

The shortest path from A to F is :

A -------> C --------> F

The length of the path is 17.

d.

The shortest path from A to G is :

A -------> C --------> F ---------> G

The length of the path is 20.