Scribd
Upload
11 views5 pages

Flight Network Routing System

The assignment involves creating a flight network routing program using C++ that calculates the shortest route between two cities based on Dijkstra's algorithm. The program includes a FlightNetwork class for managing flights and finding routes, with methods for adding flights and computing distances. A sample output demonstrates the program's functionality, showing the shortest route and total distance between two cities.

Uploaded by

abdul shaggy
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
11 views5 pages

Flight Network Routing System

The assignment involves creating a flight network routing program using C++ that calculates the shortest route between two cities based on Dijkstra's algorithm. The program includes a FlightNetwork class for managing flights and finding routes, with methods for adding flights and computing distances. A sample output demonstrates the program's functionality, showing the shortest route and total distance between two cities.

Uploaded by

abdul shaggy
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd

Department of Electrical Engineering

CIS-318 Data Structures and


Algorithms

Assignment 03

Group Members

Riyan Ali Alvi , Ghulam Abbas , Mateen Ul Haq Abbasi

Section: Electronics

Due: 03/28/2024
Flight Network Routing Program

The objective of this assignment is to design and implement a flight network routing system that
calculates the shortest route between two cities in a given flight network. The system utilizes
Dijkstra’s algorithm to compute the shortest path efficiently.

Implementation

The flight network routing system is implemented in C++ programming language. The program
consists of a FlightNetwork class which manages flights between cities and provides meth-
ods to add flights and find the shortest route between two cities.

Components

FlightNetwork Class:

• The FlightNetwork class represents the flight network system.

• It uses an unordered map to store the graph representation of the flight network, where
each city is mapped to a list of neighboring cities with associated distances.

• The addFlight method allows adding flights between cities with the associated distance.
It assumes bidirectional flights.

• The findShortestRoute method computes the shortest route between two given cities
using Dijkstra’s algorithm. It returns a pair consisting of the shortest route (as a vector of
city names) and the total distance traveled.

Main Function:

• The main function demonstrates the usage of the flight network system.

• It creates a FlightNetwork object and adds flights between cities.

• It prompts the user to input the starting city and destination city.

• It calls the findShortestRoute method to compute the shortest route.

• It outputs the shortest route and total distance traveled to the console.

Use of Parent Map:

The parent map is utilized in the findShortestRoute method to reconstruct the shortest
route once the shortest distances to all cities have been computed using Dijkstra’s algorithm.
The parent map keeps track of the predecessor of each city along the shortest path. This
information is essential for reconstructing the shortest route from the destination city back to

Page 1
the starting city. By tracing back through the parent map, the shortest path is reconstructed in
reverse order. This reversed path is then reversed again to obtain the correct order of cities from
the starting city to the destination city.

Sample Output and Code

After compilation, the code (listed in sec) produces in one case.

Figure 1: Example Output


Enter the city you are starting from: Lahore
Enter the city you want to travel to: Peshawar
Minimum distance route from Lahore to Peshawar is: Lahore -> Karachi ->
Peshawar
Total distance: 4000 miles

Listing 1: [Link]
1 #include <iostream>
2 #include <unordered_map>
3 #include <vector>
4 #include <queue>
5 #include <limits>
6 #include <algorithm>
7
8 using namespace std;
9
10 const int INF = numeric_limits<int>::max();
11
12 class FlightNetwork {
13 private:
14 unordered_map<string, unordered_map<string, int>> graph;
15
16 public:
17 void addFlight(const string& from, const string& to, int distance) {
18 graph[from][to] = distance;
19 graph[to][from] = distance; // Assuming flights are bidirectional
20 }
21
22 pair<vector<string>, int> findShortestRoute(const string& start, const←-
string& destination) {
23 priority_queue<pair<int, string>, vector<pair<int, string>>, ←-
greater<pair<int, string>>> pq;
24 unordered_map<string, int> distance;
25 unordered_map<string, string> parent;
26
27 for (const auto& entry : graph) {

Page 2
28 distance[[Link]] = INF;
29 }
30
31 distance[start] = 0;
32 [Link]({0, start});
33
34 while (![Link]()) {
35 string u = [Link]().second;
36 int dist_u = [Link]().first;
37 [Link]();
38
39 if (dist_u > distance[u]) continue;
40
41 for (const auto& neighbor : graph[u]) {
42 string v = [Link];
43 int weight = [Link];
44
45 if (distance[u] + weight < distance[v]) {
46 distance[v] = distance[u] + weight;
47 parent[v] = u;
48 [Link]({distance[v], v});
49 }
50 }
51 }
52
53 // Reconstruct the minimum distance route
54 vector<string> route;
55 string current = destination;
56 int totalDistance = distance[destination];
57
58 while (![Link]()) {
59 route.push_back(current);
60 current = parent[current];
61 }
62 reverse([Link](), [Link]());
63
64 return {route, totalDistance};
65 }
66 };
67
68 int main() {
69 FlightNetwork network;
70
71 // Adding flights to the network
72 [Link]("Lahore", "Karachi", 2500);
73 [Link]("Lahore", "Islamabad", 1000);
74 [Link]("Karachi", "Peshawar", 1500);

Page 3
75 [Link]("Islamabad", "Peshawar", 2000);
76
77 // Input from user
78 string startCity, destinationCity;
79 cout << "Enter the city you are starting from: ";
80 getline(cin, startCity);
81 cout << "Enter the city you want to travel to: ";
82 getline(cin, destinationCity);
83
84 // Finding the shortest route
85 auto result = [Link](startCity, destinationCity);
86 vector<string> minDistanceRoute = [Link];
87 int totalDistance = [Link];
88
89 // Output the minimum distance route and distance
90 cout << "\nMinimum distance route from " << startCity << " to " << ←-
destinationCity << " is:\n";
91 for (const string& city : minDistanceRoute) {
92 cout << city << " -> ";
93 }
94 cout << "\nTotal distance: " << totalDistance << " miles" << endl;
95
96 return 0;
97 }

Page 4

Common questions

Powered by AI

A pair data structure is used to return both the shortest route and the total distance, encapsulating the result of the findShortestRoute method. This choice offers simplicity and clarity in program design, providing a concise and efficient way to return multiple related values. It aligns with the C++ standards and leverages the robust STL offerings, aiding in clearer code management and further processing of results .

The Flight Network Routing Program uses Dijkstra's algorithm to find the shortest route between cities. This algorithm is suitable for this task because it efficiently computes the shortest path in a weighted graph by continually selecting the vertex with the smallest known distance, updating its neighbors, and iterating until the shortest path to the target is found .

If distances were not initialized to infinity in the findShortestRoute method, Dijkstra's algorithm would not function correctly. The algorithm relies on the initial assumption that all nodes have infinite distance from the starting point, except the start node itself, which is zero. Not initializing to infinity would result in incorrect path calculations and could lead to missing the correct shortest paths .

The parent map in the Flight Network Routing Program plays a crucial role in reconstructing the shortest route. It keeps track of the predecessor of each city along the shortest path, which allows the algorithm to trace the shortest path backward from the destination city to the starting city once the shortest distances have been computed. This information is essential in reconstructing the path in reverse order before it is reversed again to obtain the correct order from the starting city to the destination city .

The reversal of the reconstructed path in the findShortestRoute method is important because the path is initially constructed backward, from the destination city back to the starting city using the parent map. By reversing this path, the order is corrected to show the sequence from the starting city to the destination city, which is the desired output format for users .

The Flight Network Routing Program is implemented in the C++ programming language. This language is suitable for such an application due to its performance efficiency, the availability of data structures like unordered maps, and the powerful standard library features that support complex algorithms like Dijkstra's .

The Flight Network Routing Program assumes that flights between cities are bidirectional. This means that the flight distance between any two connected cities is the same in both directions, and the graph representation of the flight network reflects this assumption in storing distances .

The findShortestRoute method utilizes a priority queue to greedily select the city with the shortest known distance for processing, ensuring Dijkstra's algorithm proceeds efficiently. Simultaneously, it maintains a map of distances for each city from the starting point, updating values when shorter paths are found. The priority queue helps to efficiently retrieve the next city to process with the shortest provisional distance .

The FlightNetwork class represents the flight network using an unordered map to store the graph representation. Each city is mapped to a list of neighboring cities along with the associated distances, using a nested unordered map structure. This allows for efficient storage and retrieval of flight data between cities .

User interaction in the main function is facilitated by prompting the user to input the starting city and the destination city. This allows the program to dynamically demonstrate its capability to compute the shortest route between different pairs of cities, validating its functionality. Such interaction also demonstrates the user-friendliness and real-world applicability of the program .

You might also like