1. Initialize:
   dist[source] = 0
   dist[others] = ∞
   Insert (source, 0) into priority queue

2. While priority queue is not empty:
   u = extractMin()  // Node with smallest dist

   If u already processed → skip

   Mark u as processed

   For each neighbor v of u:
       if dist[u] + weight(u,v) < dist[v]:
           dist[v] = dist[u] + weight(u,v)
           Insert (v, dist[v]) into priority queue

    A
   / \  
  1   4
 /     \
B-------C
  \    / \
   2  1   8
    \ |   |
     D----E
       3

A → (B,1), (C,4)
B → (A,1), (C,2), (D,5)
C → (A,4), (B,2), (D,1), (E,8)
D → (B,5), (C,1), (E,3)
E → (C,8), (D,3)

#include <stdio.h>
#include <stdlib.h>
#include <limits.h>

#define V 5  // Number of vertices

// Node for priority queue
typedef struct {
    int vertex;
    int dist;
} PQNode;

// Min-Heap Priority Queue
typedef struct {
    PQNode heap[V];
    int size;
} PriorityQueue;

void initPQ(PriorityQueue* pq) {
    pq->size = 0;
}

void swap(PQNode* a, PQNode* b) {
    PQNode t = *a;
    *a = *b;
    *b = t;
}

void heapifyUp(PriorityQueue* pq, int i) {
    while (i > 0) {
        int parent = (i - 1) / 2;
        if (pq->heap[i].dist < pq->heap[parent].dist) {
            swap(&pq->heap[i], &pq->heap[parent]);
            i = parent;
        } else break;
    }
}

void heapifyDown(PriorityQueue* pq, int i) {
    int smallest = i;
    int left = 2 * i + 1;
    int right = 2 * i + 2;

    if (left < pq->size && pq->heap[left].dist < pq->heap[smallest].dist)
        smallest = left;
    if (right < pq->size && pq->heap[right].dist < pq->heap[smallest].dist)
        smallest = right;

    if (smallest != i) {
        swap(&pq->heap[i], &pq->heap[smallest]);
        heapifyDown(pq, smallest);
    }
}

void insert(PriorityQueue* pq, int vertex, int dist) {
    PQNode node = {vertex, dist};
    pq->heap[pq->size++] = node;
    heapifyUp(pq, pq->size - 1);
}

PQNode extractMin(PriorityQueue* pq) {
    PQNode min = pq->heap[0];
    pq->heap[0] = pq->heap[--pq->size];
    heapifyDown(pq, 0);
    return min;
}

int isEmpty(PriorityQueue* pq) {
    return pq->size == 0;
}

// Graph using adjacency list
typedef struct AdjNode {
    int dest;
    int weight;
    struct AdjNode* next;
} AdjNode;

typedef struct {
    AdjNode* head[V];
} Graph;

Graph* createGraph() {
    Graph* g = (Graph*)malloc(sizeof(Graph));
    for(int i = 0; i < V; i++) g->head[i] = NULL;
    return g;
}

void addEdge(Graph* g, int src, int dest, int weight) {
    AdjNode* newNode = (AdjNode*)malloc(sizeof(AdjNode));
    newNode->dest = dest;
    newNode->weight = weight;
    newNode->next = g->head[src];
    g->head[src] = newNode;

    // For undirected graph, add reverse edge
    newNode = (AdjNode*)malloc(sizeof(AdjNode));
    newNode->dest = src;
    newNode->weight = weight;
    newNode->next = g->head[dest];
    g->head[dest] = newNode;
}

// Dijkstra's Algorithm
void dijkstra(Graph* g, int src) {
    int dist[V];
    int processed[V] = {0};
    PriorityQueue pq;
    initPQ(&pq);

    for(int i = 0; i < V; i++) dist[i] = INT_MAX;
    dist[src] = 0;
    insert(&pq, src, 0);

    while (!isEmpty(&pq)) {
        PQNode curr = extractMin(&pq);
        int u = curr.vertex;

        if (processed[u]) continue;
        processed[u] = 1;

        AdjNode* temp = g->head[u];
        while (temp != NULL) {
            int v = temp->dest;
            int weight = temp->weight;

            if (!processed[v] && dist[u] + weight < dist[v]) {
                dist[v] = dist[u] + weight;
                insert(&pq, v, dist[v]);
            }
            temp = temp-> mcc;
        }
    }

    // Print result
    printf("Vertex\tDistance from %c\n", 'A' + src);
    for(int i = 0; i < V; i++) {
        printf("%c \t", 'A' + i);
        if(dist[i] == INT_MAX) printf("INF\n");
        else printf("%d\n", dist[i]);
    }
}

// Main Function
int main() {
    Graph* g = createGraph();

    addEdge(g, 0, 1, 1);  // A-B
    addEdge(g, 0, 2, 4);  // A-C
    addEdge(g, 1, 2, 2);  // B-C
    addEdge(g, 1, 3, 5);  // B-D
    addEdge(g, 2, 3, 1);  // C-D
    addEdge(g, 2, 4, 8);  // C-E
    addEdge(g, 3, 4, 3);  // D-E

    printf("Dijkstra's Algorithm (Source = A)\n");
    dijkstra(g, 0);

    return 0;
}

Dijkstra's Algorithm (Source = A)
Vertex  Distance from A
A       0
B       1
C       3
D       4
E       7

dist: [0, ∞, ∞, ∞, ∞]
PQ: (A,0)

dist: [0, 1, 4, ∞, ∞]
PQ: (B,1), (C,4)

C: 1+2=3 < 4 → Update C to 3
D: 1+5=6
PQ: (C,3), (D,6)

D: 3+1=4 < 6 → Update D to 4
E: 3+8=11

E: 4+3=7 < 11 → Update E to 7

int parent[V];

void dijkstraWithPath(Graph* g, int src) {
    // ... same as above ...
    for(int i = 0; i < V; i++) parent[i] = -1;

    // Inside relaxation:
    if (dist[u] + weight < dist[v]) {
        dist[v] = dist[u] + weight;
        parent[v] = u;  // Track path
        insert(&pq, v, dist[v]);
    }
}

// Print path
void printPath(int parent[], int v) {
    if (parent[v] == -1) {
        printf("%c ", 'A' + v);
        return;
    }
    printPath(parent, parent[v]);
    printf("→ %c ", 'A' + v);
}