Question

Question III - Shortest Path [30 Points! You wish to take a flight from city A to city I. The following graph shows the different routes you could take. The vertices are the cities (airports), and the weight on the edges are the cost of travel in KD 35 50 65 95 65 80 65 20 20 a) Apply Dijkstra's algorithm to find the minimum cost to go from city A to all other cities in the graph. Show your work in the below table. [25 Points d) Step N (B). p(B) d/C). p) dD). p(D) dE). RE) dG) p/G) dH). p(H) d) 2:0) 0 b) What is the shortest path you can take to go from city A to city I, and what is the cost to pay? 5 Points

Answer 1

Dear student,

Djikstra's Algorithm for shortest path calculation is a Greedy Approach of finding out the shortest path from any one vertex in a graph to all other vertices.

In this method, we first assign the directly connected nodes to the first node the cost of their path, and set all other nodes cost to infinity. Then, one by one we travel to each shortest connected node and check if the path from the first node to the destination node via the intermediate node is shortest or not. If it is shortest then we reassign the cost at that destination vertex.

For the given graph, let us see the table:

35 25 А 65 65 95 50 80 65 70 B. G I 30 55 65 E 20 H

Table: Step o 0 8 8 8 1 2 3 4 Selected verter B с E F H T А С 165135 65 35 160185 B. 165 35 60 1850 125 e 165|35 145 195 60 1850 125 E 165 35 145 195/60 185 0 125 H 65|35|145 195 160/85 115 125 65 35 145 195/60/85 115/125 D 6535 145 95 60/85/115/125 165/35 145/95/60/85/115 125 5 6 7 8 so, 95 0 (a) A -> B: 65 O - C :35 D : 145 А НЕ O F 60 G : 85 -> H 11 5 O : 125 o

b. As we can see above that the shortest path from city A to city I will cost 125.

The path is:

A-C-F-I

-------------------------------------------------------------------------------------------------------------------------------------------------

I hope the given solution helps clear your doubt.

Don't forget to give it a thumbs up.

Regards