Dijkstra’s Algorithm in C – Shortest Path with Step-by-Step Trace

Dijkstra’s algorithm finds the shortest path from one source vertex to all other vertices in a weighted graph with non-negative edge weights. It is a greedy algorithm: at each step it picks the unvisited vertex with the smallest known distance, marks it done, and relaxes its neighbours — updating any neighbour’s distance if a shorter route through the current vertex has been found. The result is a complete table of minimum distances and the paths used to reach them. This page gives a working C implementation, a step-by-step trace of the algorithm on a 5-vertex example, and answers to the most-searched questions about Dijkstra’s algorithm in C.

How Dijkstra’s Algorithm Works — Step by Step

Consider this weighted undirected graph (5 vertices, vertex numbers 0–4):

     0 ---4--- 1
     |       / |
     8     8   11
     |   /     |
     4 ---7--- 3 ---9--- (nothing; 3-4 not present here)
     (4 connects via 0-4 edge weight 8)

Edges: 0-1(4), 0-4(8), 1-2(8), 1-4(11), 2-3(7), 3-4(9)

Adjacency matrix (0 = no edge):

     0   1   2   3   4
0  [ 0   4   0   0   8 ]
1  [ 4   0   8   0  11 ]
2  [ 0   8   0   7   0 ]
3  [ 0   0   7   0   9 ]
4  [ 8  11   0   9   0 ]

Algorithm execution from source vertex 0:

Bold values show distances updated at each step. dist[2]=12 comes from 0→1→2 (4+8). dist[3]=17 comes from 0→4→3 (8+9), which beats 0→1→2→3 (4+8+7=19).

C Program: Dijkstra’s Algorithm

/* Dijkstra's shortest path algorithm
 * Compile: gcc -ansi -Wall -Wextra dijkstra.c -o dijkstra */
#include <stdio.h>
#define MAX 10
#define INF 1000000

/* Return the unvisited vertex with the smallest known distance.
   Returns -1 when all remaining vertices are unreachable. */
int min_vertex(int dist[], int visited[], int n)
{
    int i, min_idx = -1;
    int min = INF;
    for (i = 0; i < n; i++) {
        if (!visited[i] && dist[i] < min) {
            min = dist[i];
            min_idx = i;
        }
    }
    return min_idx;
}

/* Print the path from the source to vertex v
   by following parent[] pointers back to the root. */
void print_path(int parent[], int v)
{
    if (parent[v] == -1) { printf("%d", v); return; }
    print_path(parent, parent[v]);
    printf(" -> %d", v);
}

void dijkstra(int graph[][MAX], int n, int src)
{
    int dist[MAX], visited[MAX], parent[MAX];
    int i, j, u;

    for (i = 0; i < n; i++) {
        dist[i]    = INF;
        visited[i] = 0;
        parent[i]  = -1;
    }
    dist[src] = 0;

    for (i = 0; i < n - 1; i++) {
        u = min_vertex(dist, visited, n);
        if (u == -1) break;        /* all remaining unreachable */
        visited[u] = 1;

        for (j = 0; j < n; j++) {
            if (!visited[j] && graph[u][j] > 0 &&
                dist[u] != INF &&
                dist[u] + graph[u][j] < dist[j]) {
                dist[j]   = dist[u] + graph[u][j];
                parent[j] = u;
            }
        }
    }

    printf("Vertex   Distance   Shortest Path\n");
    printf("------   --------   -------------\n");
    for (i = 0; i < n; i++) {
        printf("  %d    ", i);
        if (dist[i] == INF)
            printf("   INF      No path from %d to %d\n", src, i);
        else {
            printf("   %5d    ", dist[i]);
            print_path(parent, i);
            printf("\n");
        }
    }
}

int main(void)
{
    int graph[MAX][MAX];
    int n, i, j, src;

    printf("Enter number of vertices (2-%d): ", MAX);
    if (scanf("%d", &n) != 1 || n < 2 || n > MAX) {
        printf("Invalid.\n"); return 1;
    }
    printf("Enter %dx%d adjacency matrix (0 = no edge):\n", n, n);
    for (i = 0; i < n; i++)
        for (j = 0; j < n; j++)
            if (scanf("%d", &graph[i][j]) != 1) {
                printf("Invalid.\n"); return 1;
            }
    printf("Enter source vertex (0-%d): ", n - 1);
    if (scanf("%d", &src) != 1 || src < 0 || src >= n) {
        printf("Invalid.\n"); return 1;
    }

    printf("\nDijkstra shortest paths from vertex %d:\n", src);
    printf("==========================================\n");
    dijkstra(graph, n, src);
    return 0;
}

Sample Output

Enter number of vertices (2-10): 5
Enter 5x5 adjacency matrix (0 = no edge):
0 4 0 0 8
4 0 8 0 11
0 8 0 7 0
0 0 7 0 9
8 11 0 9 0
Enter source vertex (0-4): 0

Dijkstra shortest paths from vertex 0:
==========================================
Vertex   Distance   Shortest Path
------   --------   -------------
  0             0    0
  1             4    0 -> 1
  2            12    0 -> 1 -> 2
  3            17    0 -> 4 -> 3
  4             8    0 -> 4

Code Explanation

• dist[] array: Stores the shortest known distance from the source to each vertex. Starts at INF (unreachable) for every vertex except the source, which starts at 0. Values are updated (relaxed) as shorter routes are discovered.
• visited[] (settled set): Once a vertex is marked visited, its shortest distance is final and will never decrease. This is the greedy invariant that makes Dijkstra’s algorithm correct for non-negative weights.
• parent[] array: Records which vertex updated each vertex’s distance. Following parent[] backwards from any destination traces the shortest path back to the source. The recursive print_path() function exploits this to print paths in forward order.
• min_vertex(): Linear scan for the unvisited vertex with minimum dist. O(V) per call, called V−1 times: total O(V²). A min-heap reduces this to O(log V) per call but is significantly more code in C.
• Relaxation condition: dist[u] + graph[u][j] < dist[j] — if the path through u is shorter than the best known path to j, update dist[j] and record u as j’s parent. The guard dist[u] != INF prevents integer overflow when u itself is unreachable.
• Disconnected graph: When min_vertex() returns -1, all remaining vertices have dist = INF and are unreachable. The loop breaks early. Unreachable vertices print “No path” in the output.

Time and Space Complexity

When Dijkstra Fails — Use Bellman-Ford Instead

Dijkstra’s greedy invariant (“once visited, always finalized”) breaks with negative-weight edges. If edge u→v has weight −5, arriving at v via a different path later might lower v’s distance further, but Dijkstra has already finalized v and won’t revisit it. For graphs with negative edges, use the Bellman-Ford algorithm, which runs in O(V·E) but handles negative weights correctly. Dijkstra also does not work on graphs with negative cycles.

Frequently Asked Questions

Related Programs

• Prim’s Algorithm in C – Minimum Spanning Tree
• BFS in C – Breadth-First Search
• DFS in C – Depth-First Search
• Floyd-Warshall Algorithm in C

Recommended books:
The C Programming Language — K&R (India) |
(US)
 | 
C Programming: A Modern Approach — K.N. King (India) |
(US)

Practice graph algorithm questions: C Aptitude Questions — or try our C Programming Quiz App on Android.