Pathway_Navigator.cpp

#include <iostream>
#include <vector>
#include <string>
#include <queue>
#include <climits>
#include <algorithm>
using namespace std;

// Number of cities
const int NUM_CITIES = 20;
 vector<string> cities = {
        "Oradea", "Zerind", "Arad", "Sibiu", "Timisoara",
        "Lugoj", "Mehadia", "Dobreta", "Craiova", "Rimnicu Vilcea",
        "Fagaras", "Pitesti", "Bucharest", "Giurgiu", "Urziceni",
        "Hirsova", "Eforie", "Vaslui", "Iasi", "Neamt"
    };



// Global adjacency lists for the graph
vector<pair<int, int>> adjListDistance[NUM_CITIES];
vector<pair<int, int>> adjListCost[NUM_CITIES];

// Bidirectional Edges
void addEdge(vector<pair<int, int>> adjList[], int u, int v, int weight) {
    adjList[u].push_back({v, weight});
    adjList[v].push_back({u, weight});
}

// Function prototypes
int getCityIndex(const string& city);
string getCityName(int index);
void makegraph_dist();
void makegraph_cost();
void dijkstra(vector<pair<int, int>> adjList[], int source, int destination);



void userInterface() {
    makegraph_dist();
    makegraph_cost();

   

    cout << "     _______       \n";
    cout << "    /|_||_ _ `.  \n";
    cout << "   (   _    _ _\\   Your Smart Route Assistance\n";
    cout << "   =`-(_)--(_)-'  \n";
    cout << "                   \n";

    while (true) {
        cout << "\nOptions:\n";
        cout << "1. Show list of available cities\n";
        cout << "2. Find shortest path based on distance\n";
        cout << "3. Find cheapest path based on cost\n";
        cout << "4. Exit\n";
        cout << "Enter your choice: ";

        int filterChoice;
        cin >> filterChoice;
        cin.ignore();

        if (filterChoice == 4) {
            cout << "Exiting program. Goodbye!\n";
            break;
        }

        if (filterChoice == 1) {
            cout << "\nList of available cities:\n";
            for (size_t i = 0; i < cities.size(); ++i) {
                cout << i << ". " << cities[i] << endl;
            }
            continue;
        }

        if (filterChoice != 2 && filterChoice != 3) {
            cout << "Invalid choice. Please select a valid option (1, 2, 3, or 4).\n";
            continue;
        }

        string sourceCity, destinationCity;
        cout << "Enter source city: ";
        getline(cin, sourceCity);
        cout << "Enter destination city: ";
        getline(cin, destinationCity);

        int source = getCityIndex(sourceCity);
        int destination = getCityIndex(destinationCity);

        if (source == -1 || destination == -1) {
            cout << "Invalid city names. Please check your input.\n";
            continue;
        }

        if (filterChoice == 2) {
            cout << "\nFinding shortest path based on distance:\n";
            dijkstra(adjListDistance, source, destination);
        } else if (filterChoice == 3) {
            cout << "\nFinding shortest path based on cost:\n";
            dijkstra(adjListCost, source, destination);
        }
    }
}



// A function to get the city index from its name
int getCityIndex(const string& city) {
    string inputCity = city;
    transform(inputCity.begin(), inputCity.end(), inputCity.begin(), ::tolower);
    
    for (int i = 0; i < cities.size(); i++) {
        string lowerCity = cities[i];
        transform(lowerCity.begin(), lowerCity.end(), lowerCity.begin(), ::tolower);
        if (lowerCity == inputCity)
            return i;
    }
    return -1;  // City not found
}



// A function to get the city name from its index
string getCityName(int index) {

    if (index >= 0 && index < cities.size()) {
        return cities[index];
    }
    return "Unknown";
}

// Function to create the distance-based graph
void makegraph_dist() {
	
	addEdge(adjListDistance, getCityIndex("Oradea"), getCityIndex("Zerind"), 71);
	addEdge(adjListDistance, getCityIndex("Oradea"), getCityIndex("Sibiu"), 151);
	addEdge(adjListDistance, getCityIndex("Zerind"), getCityIndex("Arad"), 75);
	addEdge(adjListDistance, getCityIndex("Arad"), getCityIndex("Sibiu"), 140);
	addEdge(adjListDistance, getCityIndex("Arad"), getCityIndex("Timisoara"), 118);
	addEdge(adjListDistance, getCityIndex("Timisoara"), getCityIndex("Lugoj"), 111);
	addEdge(adjListDistance, getCityIndex("Lugoj"), getCityIndex("Mehadia"), 70);
	addEdge(adjListDistance, getCityIndex("Mehadia"), getCityIndex("Dobreta"), 75);
	addEdge(adjListDistance, getCityIndex("Dobreta"), getCityIndex("Craiova"), 120);
	addEdge(adjListDistance, getCityIndex("Sibiu"), getCityIndex("Fagaras"), 99);
	addEdge(adjListDistance, getCityIndex("Sibiu"), getCityIndex("Rimnicu Vilcea"), 80);
	addEdge(adjListDistance, getCityIndex("Rimnicu Vilcea"), getCityIndex("Craiova"), 146);
	addEdge(adjListDistance, getCityIndex("Rimnicu Vilcea"), getCityIndex("Pitesti"), 97);
	addEdge(adjListDistance, getCityIndex("Craiova"), getCityIndex("Pitesti"), 138);
	addEdge(adjListDistance, getCityIndex("Fagaras"), getCityIndex("Bucharest"), 211);
	addEdge(adjListDistance, getCityIndex("Pitesti"), getCityIndex("Bucharest"), 101);
	addEdge(adjListDistance, getCityIndex("Bucharest"), getCityIndex("Giurgiu"), 90);
	addEdge(adjListDistance, getCityIndex("Bucharest"), getCityIndex("Urziceni"), 85);
	addEdge(adjListDistance, getCityIndex("Urziceni"), getCityIndex("Hirsova"), 98);
	addEdge(adjListDistance, getCityIndex("Hirsova"), getCityIndex("Eforie"), 86);
	addEdge(adjListDistance, getCityIndex("Urziceni"), getCityIndex("Vaslui"), 142);
	addEdge(adjListDistance, getCityIndex("Vaslui"), getCityIndex("Iasi"), 92);
	addEdge(adjListDistance, getCityIndex("Iasi"), getCityIndex("Neamt"), 87);

}

// Function to create the time-based graph
void makegraph_cost() {
   addEdge(adjListCost, getCityIndex("Oradea"), getCityIndex("Zerind"), 51);
	addEdge(adjListCost, getCityIndex("Oradea"), getCityIndex("Sibiu"), 130);
	addEdge(adjListCost, getCityIndex("Zerind"), getCityIndex("Arad"), 60);
	addEdge(adjListCost, getCityIndex("Arad"), getCityIndex("Sibiu"), 135);
	addEdge(adjListCost, getCityIndex("Arad"), getCityIndex("Timisoara"), 111);
	addEdge(adjListCost, getCityIndex("Timisoara"), getCityIndex("Lugoj"), 105);
	addEdge(adjListCost, getCityIndex("Lugoj"), getCityIndex("Mehadia"), 65);
	addEdge(adjListCost, getCityIndex("Mehadia"), getCityIndex("Dobreta"), 70);
	addEdge(adjListCost, getCityIndex("Dobreta"), getCityIndex("Craiova"), 115);
	addEdge(adjListCost, getCityIndex("Sibiu"), getCityIndex("Fagaras"), 92);
	addEdge(adjListCost, getCityIndex("Sibiu"), getCityIndex("Rimnicu Vilcea"), 75);
	addEdge(adjListCost, getCityIndex("Rimnicu Vilcea"), getCityIndex("Craiova"), 140);
	addEdge(adjListCost, getCityIndex("Rimnicu Vilcea"), getCityIndex("Pitesti"), 92);
	addEdge(adjListCost, getCityIndex("Craiova"), getCityIndex("Pitesti"), 135);
	addEdge(adjListCost, getCityIndex("Fagaras"), getCityIndex("Bucharest"), 209);
	addEdge(adjListCost, getCityIndex("Pitesti"), getCityIndex("Bucharest"), 99);
	addEdge(adjListCost, getCityIndex("Bucharest"), getCityIndex("Giurgiu"), 85);
	addEdge(adjListCost, getCityIndex("Bucharest"), getCityIndex("Urziceni"), 80);
	addEdge(adjListCost, getCityIndex("Urziceni"), getCityIndex("Hirsova"), 95);
	addEdge(adjListCost, getCityIndex("Hirsova"), getCityIndex("Eforie"), 83);
	addEdge(adjListCost, getCityIndex("Urziceni"), getCityIndex("Vaslui"), 140);
	addEdge(adjListCost, getCityIndex("Vaslui"), getCityIndex("Iasi"), 88);
	addEdge(adjListCost, getCityIndex("Iasi"), getCityIndex("Neamt"), 85);

}

// Dijkstra's Algorithm to find the shortest path
void dijkstra(vector<pair<int, int>> adjList[], int source, int destination) {
    vector<int> distance(NUM_CITIES, INT_MAX);
    vector<int> parent(NUM_CITIES, -1);
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> pq;

    distance[source] = 0;
    pq.push({0, source});
 
    while (!pq.empty()) {
        int currentDist = pq.top().first;
        int currentCity = pq.top().second;
        pq.pop();

        if (currentDist > distance[currentCity]) continue;

        for (auto& neighbor : adjList[currentCity]) {
            int nextCity = neighbor.first;
            int weight = neighbor.second;

            if (distance[currentCity] + weight < distance[nextCity]) {
                distance[nextCity] = distance[currentCity] + weight;
                parent[nextCity] = currentCity;
                pq.push({distance[nextCity], nextCity});
            }
        }
    }

    if (distance[destination] == INT_MAX) {
        cout << "No path found from " << getCityName(source) << " to " << getCityName(destination) << endl;
        return;
    }

    vector<int> path;
    for (int at = destination; at != -1; at = parent[at]) {
        path.push_back(at);
    }
    reverse(path.begin(), path.end());

    cout << "Shortest path from " << getCityName(source) << " to " << getCityName(destination) << ":\n";
    for (int i = 0; i < path.size(); i++) {
        cout << getCityName(path[i]);
        if (i != path.size() - 1) cout << " -> ";
    }
    cout << "\nTotal cost: " << distance[destination] << endl;
    cout<< "Ready to roll. Go now!"<< endl;
}
int main() {
    userInterface();
    return 0;
}