djistra-alg.cpp

#include <iostream>
using namespace std;

class Graph {
    int **adjMatrix;
    int vertices;

public:
    Graph(int v) {
        vertices = v;
        adjMatrix = new int*[vertices];
        for (int i = 0; i < vertices; i++) {
            adjMatrix[i] = new int[vertices];
            for (int j = 0; j < vertices; j++) {
                adjMatrix[i][j] = (i == j) ? 0 : 1e9; // Large value for no direct edge
            }
        }
    }

    void addEdge(int u, int v, int w) {
        adjMatrix[u][v] = w;
        adjMatrix[v][u] = w; // Remove this line for directed graphs
    }

    void dijkstra(int start) {
        int *dist = new int[vertices];
        int *visited = new int[vertices];

        for (int i = 0; i < vertices; i++) {
            dist[i] = 1e9; // Initialize distances to a large value
            visited[i] = 0;
        }

        dist[start] = 0;

        for (int count = 0; count < vertices - 1; count++) {
            int minDist = 1e9, minIndex = -1;

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

            visited[minIndex] = 1;

            for (int v = 0; v < vertices; v++) {
                if (!visited[v] && adjMatrix[minIndex][v] != 1e9 && 
                    dist[minIndex] + adjMatrix[minIndex][v] < dist[v]) {
                    dist[v] = dist[minIndex] + adjMatrix[minIndex][v];
                }
            }
        }

        cout << "Shortest distances from node " << start << ":\n";
        for (int i = 0; i < vertices; i++) {
            cout << "To " << i << " -> " << (dist[i] == 1e9 ? -1 : dist[i]) << endl;
        }

        delete[] dist;
        delete[] visited;
    }

    ~Graph() {
        for (int i = 0; i < vertices; i++) {
            delete[] adjMatrix[i];
        }
        delete[] adjMatrix;
    }
};

int main() {
    int vertices, edges, u, v, w, start;
    cout << "Enter number of vertices: ";
    cin >> vertices;
    Graph g(vertices);

    cout << "Enter number of edges: ";
    cin >> edges;
    cout << "Enter edges (u v w):" << endl;
    for (int i = 0; i < edges; i++) {
        cin >> u >> v >> w;
        g.addEdge(u, v, w);
    }

    cout << "Enter starting node for Dijkstra's Algorithm: ";
    cin >> start;

    g.dijkstra(start);

    return 0;
}