Dijkstra's Shortest Path Algorithm in C

Dijkstra's algorithm finds the shortest path between nodes in a weighted graph with non-negative edge costs using greedy vertex relaxation.

Dijkstra's Algorithm finds the shortest path from a single source vertex to all other vertices in a weighted graph with non-negative edge weights. It is widely used in network packet routing protocols (OSPF) and GPS navigation systems.

The algorithm maintains a set of visited vertices and an array of minimum distances. At each step, it greedily selects the unvisited vertex with the smallest provisional distance and relaxes all outgoing edges to its neighbors.

In this C implementation, an adjacency matrix represents the graph. While an adjacency matrix is simple and clean for dense graphs with O(V²) complexity, sparse graphs in production typically pair adjacency lists with a binary min-heap priority queue for O((V + E) log V) efficiency.

Interactive Runnable C Implementation

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

#define V 5

int minDistance(int dist[], bool sptSet[]) {
    int min = INT_MAX, min_index = -1;
    for (int v = 0; v < V; v++) {
        if (!sptSet[v] && dist[v] <= min) {
            min = dist[v];
            min_index = v;
        }
    }
    return min_index;
}

void dijkstra(int graph[V][V], int src) {
    int dist[V];
    bool sptSet[V];

    for (int i = 0; i < V; i++) {
        dist[i] = INT_MAX;
        sptSet[i] = false;
    }

    dist[src] = 0;

    for (int count = 0; count < V - 1; count++) {
        int u = minDistance(dist, sptSet);
        sptSet[u] = true;

        for (int v = 0; v < V; v++) {
            if (!sptSet[v] && graph[u][v] && dist[u] != INT_MAX
                && dist[u] + graph[u][v] < dist[v]) {
                dist[v] = dist[u] + graph[u][v];
            }
        }
    }

    printf("Vertex 	 Distance from Source (%d)\n", src);
    for (int i = 0; i < V; i++) printf("%d 		 %d\n", i, dist[i]);
}

int main() {
    int graph[V][V] = {
        {0, 4, 0, 8, 0},
        {4, 0, 8, 11, 0},
        {0, 8, 0, 7, 2},
        {8, 11, 7, 0, 9},
        {0, 0, 2, 9, 0}
    };
    dijkstra(graph, 0);
    return 0;
}

Open example in compiler

Expected Output

Vertex 	 Distance from Source (0)
0 		 0
1 		 4
2 		 12
3 		 8
4 		 14