Graph Shortest Path Algorithm

#include <iostream>
#include <vector>
#include <queue>
#include <climits>
#include <stack>

using namespace std;

// Representing a graph as an adjacency matrix for simplicity
class Graph {
public:
    int vertices;  // Number of locations
    vector<vector<int>> adjMatrix;  // Adjacency matrix to store traffic times

    Graph(int v) : vertices(v) {
        adjMatrix.resize(v, vector<int>(v, INT_MAX)); // Initialize all distances to infinity
    }

    // Add an edge between two locations with a traffic delay time
    void addEdge(int src, int dest, int time) {
        adjMatrix[src][dest] = time;
        adjMatrix[dest][src] = time;  // Assuming it's an undirected graph
    }

    // Dijkstra's algorithm to find the shortest path
    vector<int> dijkstra(int src, vector<int>& parent) {
        vector<int> dist(vertices, INT_MAX);
        dist[src] = 0;
        priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
        pq.push({0, src});

        while (!pq.empty()) {
            int u = pq.top().second;
            pq.pop();

            // Check all the neighbors of the current node
            for (int v = 0; v < vertices; ++v) {
                if (adjMatrix[u][v] != INT_MAX) {
                    int newDist = dist[u] + adjMatrix[u][v];
                    if (newDist < dist[v]) {
                        dist[v] = newDist;
                        parent[v] = u; // Record the path
                        pq.push({dist[v], v});
                    }
                }
            }
        }

        return dist;
    }

    void displayShortestPath(int src, int dest) {
        vector<int> parent(vertices, -1); // To store the path
        vector<int> dist = dijkstra(src, parent);

        if (dist[dest] == INT_MAX) {
            cout << "No path found between location " << src << " and " << dest << endl;
            return;
        }

        cout << "Shortest time from location " << src << " to location " << dest << ": " << dist[dest] << " minutes" << endl;

        // Reconstruct and display the path
        stack<int> path;
        int current = dest;
        while (current != -1) {
            path.push(current);
            current = parent[current];
        }

        cout << "Path taken: ";
        while (!path.empty()) {
            cout << path.top() << " ";
            path.pop();
        }
        cout << endl;
    }
};

int main() {
    int locations = 5;  // Number of locations (vertices)
    Graph g(locations);

    // Adding edges with random traffic delays in minutes (you can replace it with real data)
    g.addEdge(0, 1, 10);  // Example: Bus route from location 0 to 1 with 10 minutes traffic delay
    g.addEdge(1, 2, 15);  // Example: Metro route from location 1 to 2 with 15 minutes traffic delay
    g.addEdge(2, 3, 30);  // Example: Bus route from location 2 to 3 with 30 minutes traffic delay
    g.addEdge(3, 4, 10);  // Example: Metro route from location 3 to 4 with 10 minutes traffic delay
    g.addEdge(0, 2, 50);  // Example: Bus route from location 0 to 2 with 50 minutes traffic delay
    g.addEdge(1, 3, 20);  // Example: Metro route from location 1 to 3 with 20 minutes traffic delay

    int source, destination;

    // Get user input for source and destination locations
    cout << "Enter the source location (0 to " << locations - 1 << "): ";
    cin >> source;
    cout << "Enter the destination location (0 to " << locations - 1 << "): ";
    cin >> destination;

    // Validate the input
    if (source < 0 || source >= locations || destination < 0 || destination >= locations) {
        cout << "Invalid source or destination location!" << endl;
        return 1;
    }

    // Display shortest time and path from source to destination
    g.displayShortestPath(source, destination);

    return 0;
}
        

Run Code