Scribd
Upload
8 views4 pages

Daa Project

Uploaded by

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

Daa Project

Uploaded by

yashika.bhatia0522
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
You are on page 1/ 4

#include <iostream>

#include <vector>

#include <unordered_map>

#include <queue>

#include <limits>

#include <string>

#include <algorithm> // Include this header for std::reverse

using namespace std;

struct Station {

string name;

string corridor;

unordered_map<string, double> connections; // connected station and distance

};

class Graph {

private:

unordered_map<string, Station> stations;

public:

void addStation(const string& name, const string& corridor) {

Station newStation{name, corridor};

stations[name] = newStation;

void addConnection(const string& station1, const string& station2, double distance) {

stations[station1].connections[station2] = distance;

stations[station2].connections[station1] = distance; // undirected graph

}
pair<vector<string>, double> findShortestPath(const string& source, const string& destination) {

unordered_map<string, double> distances;

unordered_map<string, string> predecessors;

priority_queue<pair<double, string>, vector<pair<double, string>>, greater<pair<double,


string>>> pq;

for (const auto& station : stations) {

distances[station.first] = numeric_limits<double>::infinity();

distances[source] = 0;

pq.push({0, source});

while (!pq.empty()) {

string current = pq.top().second;

pq.pop();

if (current == destination) break;

for (const auto& neighbor : stations[current].connections) {

double newDist = distances[current] + neighbor.second;

if (newDist < distances[neighbor.first]) {

distances[neighbor.first] = newDist;

predecessors[neighbor.first] = current;

pq.push({newDist, neighbor.first});

vector<string> path;

double totalFare = distances[destination];

for (string at = destination; !at.empty(); at = predecessors[at]) {


path.push_back(at);

reverse(path.begin(), path.end());

return {path, totalFare};

};

int main() {

Graph delhiMetro;

// Adding stations

delhiMetro.addStation("delhi", "Corridor1");

delhiMetro.addStation("dilshad garden", "Corridor1");

delhiMetro.addStation("rohini", "Corridor2");

delhiMetro.addStation("faridabad", "Corridor2");

// Adding connections (distances)

delhiMetro.addConnection("delhi", "dilshad garden", 5.0);

delhiMetro.addConnection("dilshad garden", "rohini", 10.0);

delhiMetro.addConnection("delhi", "rohini", 15.0);

delhiMetro.addConnection("rohini", "faridabad", 20.0);

string source, destination;

cout << "Enter source station: ";

cin >> source;

cout << "Enter destination station: ";

cin >> destination;

auto result = delhiMetro.findShortestPath(source, destination);

cout << "Shortest path: ";

for (const auto& station : result.first) {


cout << station << " ";

cout << "\nTotal fare (distance): " << result.second << endl;

return 0;

You might also like