The Flight Network Map (FNM) is a project for designing and implementing effective graph

analysis algorithms to efficiently calculate lowest-cost paths for a variety of criteria. You will be

given a list of cities (calculate coordinate locations using map if needed), and a list of

international airport flights (edges). Using these lists, you will build a representation of the

associated graph, and analyze it using any algorithm to design minimum cost tree connecting a

set of cities and then answer specific questions such as shortest distance between cities,

minimum number of hops between a pair of source and destination cities.

Consider you have to travel from USA to Multan. You can travel by air from USA to Karachi

international airport via connecting flight from Islamabad and then drive to Multan but make

sure with connecting at least four different cities from the given list to reach destination. The

nodes of the graph will represent countries/cities and edge path costs will be calculated by

using driving distances between pairs of cities connected by a direct road (for simplicity, ignore

red lights, stop signs, toll roads and other obstructions) and speed (Last two digits of your

registration number), calculated time will be taken as cost.

Cities (Hyderabad, Makli, Sangar, Larkana, Sadiqabad, Kot Addu, Jacobabad, Derabugti)

Tasks

(a) Compute the best path using the criterion of minimizing the total time taken (Cost) to reach

the destination.

(b) Using the algorithm find a) the source vertex, b) the shortest path tree, and c) the resulting

d-values.

(c) Implement OSPF algorithm code for the city wise configuration on packet tracer and show

the results.