This is a weighted graph where the vertices represent cities and the edges indic

Question

This is a weighted graph where the vertices represent cities and the edges indicate the Air Busters Airlines flights that connect the cities. The weights attached to the edges represent the air distances between the pairs of cities. Here is an array-based implementation that will find the shortest path from Washington to Chicago. Complete the implementation such that the user can enter a city from which they are leaving and a city they want to arrive in and the program will display the shortest path possible showing the cities along the way.

Explanation / Answer

Since you have not mentioned the language, let me go the generic concept and aproach. We shall be using Dijsktra's algorithm to solve the problem using the graph.

Given a graph and a source vertex in graph, find shortest paths from source to all vertices in the given graph. This algo is the simplest, but fails to detect -ve cycle. Since we do not have -ve edges, it is very convenient and easy to implent dijsktra.

ALGO:

1) Create a set sptSet (shortest path tree set) that keeps track of vertices included in shortest path tree, i.e., whose minimum distance from source is calculated and finalized. Initially, this set is empty.
2) Assign a distance value to all vertices in the input graph. Initialize all distance values as INFINITE. Assign distance value as 0 for the source vertex so that it is picked first.
3) While sptSet doesn’t include all vertices
….a) Pick a vertex u which is not there in sptSetand has minimum distance value.
….b) Include u to sptSet.
….c) Update distance value of all adjacent vertices of u. To update the distance values, iterate through all adjacent vertices. For every adjacent vertex v, if sum of distance value of u (from source) and weight of edge u-v, is less than the distance value of v, then update the distance value of v

*If you need code in java/c++ let me know. Will update you, but that might take time of 1-3 days :(

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.