Use Dijkstra\'a algorithm to find the \"shortest path\" between any two airports

Question

Use Dijkstra'a algorithm to find the "shortest path" between any two airports. http://openflights.org/data.html (Links to an external site.) has all of the information that you will need --- airport designators, airline designators, airline routes and so forth. If multiple airlines serve the same route, such as Delta and British Airways from Los Angeles to London, BOTH routes must be printed in order to give the end-user a choice of airlines (frequent flyer miles really pay off!)

The input for your program must be a valid airport code for the origin and a valid airport code for the destination.

The output must be an itinerary, such as:

Leave LAX (Los Angeles) on American Airways after flying 2,500 miles

Change planes at ANT (Atlanta) to American Airlines and fly 1,000 miles

Arrive at MiA (Miami)

HINT: The "raw" data at the website listed above is "way toooooooooo" much to put into your program all at once. What you will need to do is to "sanitize" it and make it into an XML file.This means that a separate "sanitizing" or "pre-processing" program has to be written. Distances between airports are not provided directly; you will have to compute the distance between airports by using the Great Circle method within your program as it loads the XML file

Explanation / Answer

Dijkstra's Algorithm-
In this algorithm each vertex is marked as either known or unknown. A tentative distance dv is kept for each vertex, as before. This distance turns out to be the shortest path length from s to v using only known vertices as intermediates

"shortest path" between any two airports-

#include "Graph.h"

void void Shortestpath(Graph const &graph, int a, vector &dist, vector &pred)
{

const int b = graph.numVer( );
pred.assi(b, -1);
dist.assi(b, num_lim<int>::M( ));
vector<bool> visited(b);
dist[a] = 0;

while (true)
{
int g = -1;
int ac = num_lim<int>::m( );

for (int i = 0; i < b; i++)
{
if (!visited[i] && dist[i] < sd)
{
ac = dist[i];
g = i;
}
}
if (g == -1)
{
break;

visited[g] = true;

for (VertexList::const_iterator ci = graph.begin(g); ci != graph.end(g); ++ci)
{
int t = ci->first;
long newLen = dist[g];
nwL += ci->second;

if (nwL < dist[t])
{
dist[t] = nwL;
pred[t] = g;
}
}
}
}

Related Questions

Navigate

• Browse (All)
• Browse U
• Subjects

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