djkstrapath.cpp

#include <iostream>
using namespace std;

class Dijkstra {
    int** graph;
    int* dist;
    bool* visited;
    int* parent;
    int vertices;

public:
    Dijkstra() {
        cout << "Enter number of vertices: ";
        cin >> vertices;

        // Initialize matrix
        graph = new int*[vertices];
        for (int i = 0; i < vertices; i++) {
            graph[i] = new int[vertices];
            for (int j = 0; j < vertices; j++) {
                graph[i][j] = 0; // No edge initially
            }
        }

        dist = new int[vertices];
        visited = new bool[vertices];
        parent = new int[vertices];

        int edges;
        cout << "Enter number of edges: ";
        cin >> edges;

        cout << "Enter edges in format: u v weight\n";
        for (int i = 0; i < edges; i++) {
            int u, v, w;
            cin >> u >> v >> w;
            graph[u][v] = w;
            graph[v][u] = w; // Comment this line if graph is directed
        }
    }

    void findShortestPaths(int start) {
        for (int i = 0; i < vertices; i++) {
            dist[i] = 1e9;
            visited[i] = false;
            parent[i] = -1;
        }

        dist[start] = 0;

        for (int count = 0; count < vertices - 1; count++) {
            int u = getMinVertex();
            visited[u] = true;

            for (int v = 0; v < vertices; v++) {
                if (!visited[v] && graph[u][v] != 0 && dist[u] + graph[u][v] < dist[v]) {
                    dist[v] = dist[u] + graph[u][v];
                    parent[v] = u;
                }
            }
        }

        display(start);
    }

    int getMinVertex() {
        int min = 1e9, minIndex = -1;
        for (int i = 0; i < vertices; i++) {
            if (!visited[i] && dist[i] < min) {
                min = dist[i];
                minIndex = i;
            }
        }
        return minIndex;
    }

    void printPath(int node) {
        if (parent[node] == -1) {
            cout << node;
            return;
        }
        printPath(parent[node]);
        cout << " -> " << node;
    }

    void display(int start) {
        cout << "\nShortest paths from vertex " << start << ":\n";
        for (int i = 0; i < vertices; i++) {
            cout << "To " << i << " (Cost: ";
            if (dist[i] == 1e9)
                cout << "Unreachable): No path\n";
            else {
                cout << dist[i] << "): Path: ";
                printPath(i);
                cout << endl;
            }
        }
    }

    ~Dijkstra() {
        for (int i = 0; i < vertices; i++) {
            delete[] graph[i];
        }
        delete[] graph;
        delete[] dist;
        delete[] visited;
        delete[] parent;
    }
};

int main() {
    Dijkstra d;
    int start;
    cout << "Enter source vertex: ";
    cin >> start;
    d.findShortestPaths(start);
    return 0;
}