djkstraprior.cpp

#include <iostream>
using namespace std;

class PriorityQueue {
    int* heap;
    int* dist; // parallel array for distances
    int size;
    int capacity;

    void heapifyUp(int index) {
        while (index > 0) {
            int parent = (index - 1) / 2;
            if (dist[heap[parent]] > dist[heap[index]]) {
                int temp = heap[parent];
                heap[parent] = heap[index];
                heap[index] = temp;
                index = parent;
            } else {
                break;
            }
        }
    }

    void heapifyDown(int index) {
        while (2 * index + 1 < size) {
            int left = 2 * index + 1;
            int right = 2 * index + 2;
            int smallest = index;

            if (left < size && dist[heap[left]] < dist[heap[smallest]]) {
                smallest = left;
            }
            if (right < size && dist[heap[right]] < dist[heap[smallest]]) {
                smallest = right;
            }

            if (smallest != index) {
                int temp = heap[index];
                heap[index] = heap[smallest];
                heap[smallest] = temp;
                index = smallest;
            } else {
                break;
            }
        }
    }

public:
    PriorityQueue(int cap, int* d) {
        capacity = cap;
        dist = d;
        heap = new int[capacity];
        size = 0;
    }

    void push(int val) {
        if (size == capacity) {
            cout << "Priority Queue is full\n";
            return;
        }
        heap[size] = val;
        heapifyUp(size);
        size++;
    }

    int pop() {
        if (size == 0) {
            return -1;
        }
        int root = heap[0];
        heap[0] = heap[size - 1];
        size--;
        heapifyDown(0);
        return root;
    }

    bool isEmpty() {
        return size == 0;
    }

    ~PriorityQueue() {
        delete[] heap;
    }
};

void dijkstra(int** adj, int V, int start) {
    int* dist = new int[V];
    bool* visited = new bool[V];

    for (int i = 0; i < V; i++) {
        dist[i] = 1e9; // large value as infinity
        visited[i] = false;
    }

    dist[start] = 0;

    PriorityQueue pq(V, dist);
    pq.push(start);

    while (!pq.isEmpty()) {
        int u = pq.pop();

        if (visited[u]) {
            continue;
        }
        visited[u] = true;

        for (int v = 0; v < V; v++) {
            if (adj[u][v] != 0) {
                if (dist[u] + adj[u][v] < dist[v]) {
                    dist[v] = dist[u] + adj[u][v];
                    pq.push(v);
                }
            }
        }
    }

    cout << "Shortest distances from vertex " << start << ":\n";
    for (int i = 0; i < V; i++) {
        if (dist[i] == 1e9)
            cout << "Vertex " << i << ": Unreachable\n";
        else
            cout << "Vertex " << i << ": " << dist[i] << endl;
    }

    delete[] dist;
    delete[] visited;
}

int main() {
    int V, E;
    cout << "Enter number of vertices and edges: ";
    cin >> V >> E;

    int** adj = new int*[V];
    for (int i = 0; i < V; i++) {
        adj[i] = new int[V];
        for (int j = 0; j < V; j++) {
            adj[i][j] = 0;
        }
    }

    cout << "Enter edges (u v w):\n";
    for (int i = 0; i < E; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        adj[u][v] = w;
        adj[v][u] = w; // for undirected graphs
    }

    int start;
    cout << "Enter starting vertex for Dijkstra: ";
    cin >> start;

    dijkstra(adj, V, start);

    for (int i = 0; i < V; i++) {
        delete[] adj[i];
    }
    delete[] adj;

    return 0;
}