The following information pertains to the next 4 problems Ap

The following information pertains to the next 4 problems. Apply Dijkstra\'s Algorithm on the graph above. Source vertex is 0. Provide shortest-path from the source vertex to every other vertex in the graph, e.g., shortest-path(0, 7) is {0, 4, 7}. Provide path cost (sum of weight for all edges in path) for all the paths derived from problem 5. above. Highlight the resulting paths. Provide Adjacency list representation.

Solution

Dijkstras algorithm helps in finding the shortest path in the graphs. so, lets begin with the above given graph.

5. shortest path from source vertex to other vertex in the graph.

Initial vertex is 0

for node 1: 0---->1 and 0---->4----->2-------->1

so the shortest path is calculated as min{ 0---->1 ,0------>4-------->2------->1)

min{5,6+4+8}=5.

so the shortest path to reach node 1 is 0---->1

similarly for node 4: The node 4 has only one direction so, 0----->4(6)

for node 2:Node 2 is same as node 4 since it even has unique(single) direction 0---->4---->2(10)

for node 6:   min{0---->1---->6 , 0----->4---->6)

min{5+7 ,6+7} = 0----->1---->6

for node 7: as given in the question it is 0--->4--->7 since min{ 0--->4--->7 ,0---->1--->6--->7}

for node 5: min{0--->1--->5 ,0---->1--->6---->5 ,0---->4---->7---->5}   

min{10,17,14} ==0---->1---->5

dikshtras algorithms helps in finding the shortest path by finding the adjacent nodes .so for node 3 there is no adjacenct node so,node can be neglected....since there is no direction to node 3.

6. provide path cost : node 1: 0--->1 =5

node 4 :0---->4 =6

node 2:0----->4---->2=10

node 6:0--->1--->6=12

node 5:10 (0--->1--->5)

node 7:0--->4--->7 =10

4. ADJACENCY lIST REPRESENTATION:

0 ------->1------>4   

1 ------->5------->6

2 ------->1

4 ------->2------>6------>7

5

6 ------->5----->7

7 ------->5

3   ------->5