Question

Trace through of Dijkstra’s Algorithm, using vertex v5 as the source vertex.

Here is adjacency matrix representing the graph with n = 6 vertices:

	1	2	3	4	5	6
1	0	999	5	8	999	4
2	9	0	999	999	12	3
3	999	10	0	2	9	999
4	999	999	999	0	999	999
5	999	7	17	999	0	11
6	5	999	11	16	2	0

            Initially we have: vnear = 5. Fill array performing initiation.

	1	2	3	4	5	6
touch
length

             Repeat the main loop 5 times:

Hint: copy and paste following table five times, then fill all values for arrays.

            vnear =

	1	2	3	4	5	6
touch
length

Answer 1

Step 1 Let us first discuss about Dijkstra algorithm

Step 2 Using Dijkstra algorithm

1)vnear= Intially

	1	2	3	4	5	6
length					0
touch	N	N	N	N	-	N

2)vnear= 5

	1	2	3	4	5	6
length	999	7	17	999	0	11
touch	5	5	5	5	-	5

3)vnear = 2

	1	2	3	4	5	6
touch	2	5	5	5	-	2
length	16	7	17	999	0	10

4)vnear = 6

	1	2	3	4	5	6
touch	6	5	5	6	-	2
length	15	7	17	26	0	10

5)vnear = 1

	1	2	3	4	5	6
touch	6	5	5	1	-	2
length	15	7	17	23	0	10

6)vnear = 3

	1	2	3	4	5	6
touch	6	5	5	3	_	2
length	15	7	17	19	0	10

At the end ,node 4 will be selected finally