Offensive Security Researcher & Quantum Cryptography Analyst

Dijkstra’s Shortest-Path Algorithm: Working, Explanation, and Implementation

Abdul Wahab Junaid
Dijkstra's Shortest-Path algorithm and working of this algorithm

Dijkstra's Shortest-Path algorithm and working of this algorithm

When I first sat down to understand how computers find the “shortest” way from one point to another — whether that’s a road network, a computer network, or a dependency graph — Dijkstra’s algorithm is the name that comes up almost immediately. I want to walk through it the way I understood it myself: as a systematic, greedy method for finding the shortest path from a single source node to every other node in a graph, as long as none of the edge weights are negative. It matters because so much of modern routing — GPS navigation, network packet routing, even some AI planning systems — rests on this one idea.

History and Background

I learned that this algorithm was conceived by the Dutch computer scientist Edsger W. Dijkstra in 1956, and he published it in 1959. What I find charming about the origin story is that he designed it in about twenty minutes, without pen or paper, while thinking about how to demonstrate the capabilities of a new computer (the ARMAC) to a general audience — he wanted a problem that a layperson could understand and a computer could solve impressively. He picked the shortest route between two cities in the Netherlands. Since then, the algorithm has become one of the most cited and most implemented algorithms in computer science, forming the backbone of routing protocols like OSPF and IS-IS.

Problem Statement

I would state the problem like this: given a weighted, directed or undirected graph $G = (V, E)$ with non-negative edge weights, and a designated source vertex $s$, I want to determine the shortest possible distance from $s$ to every other vertex in $V$, and ideally reconstruct the actual path.

Core Concepts

Before I get into the mechanics, I want to lay out the vocabulary I rely on:

How It Works

Here is the sequence I follow when running the algorithm by hand:

  1. I assign a tentative distance value to every vertex: zero for the source, infinity for all others.
  2. I mark all vertices as unvisited and put them in a set of “vertices to check.”
  3. I set the source as the current vertex.
  4. For the current vertex, I look at all of its unvisited neighbors and calculate their tentative distance through the current vertex. If this new distance is smaller than the previously recorded one, I update it.
  5. Once I’ve considered all neighbors of the current vertex, I mark it as visited — it is removed from the unvisited set and will never be checked again.
  6. I pick the unvisited vertex with the smallest tentative distance and make it the new current vertex.
  7. I repeat steps 4–6 until every vertex has been visited, or the smallest tentative distance among unvisited vertices is infinity (meaning remaining vertices are unreachable).

Working Principle

The internal logic rests on a greedy assumption: once I’ve settled on the shortest distance to a vertex, that distance can never be improved later — because all edge weights are non-negative, any alternative path would have to pass through an unvisited vertex whose current distance is already at least as large. This is exactly why Dijkstra’s algorithm fails on graphs with negative weights: the greedy “lock-in” assumption breaks down if a later, cheaper edge could reduce a distance I already finalized.

Mathematical Foundation

I define $d(v)$ as the tentative distance to vertex $v$, and $w(u,v)$ as the weight of edge $(u,v)$. The relaxation step is expressed as:

$$ d(v) = \min\big(d(v),\ d(u) + w(u,v)\big) $$

The algorithm terminates with the guarantee:

$$ d(v) = \delta(s,v) \quad \text{for every } v \in V $$

where $\delta(s,v)$ is the true shortest-path distance from $s$ to $v$.

Using a binary heap as the priority queue, the overall running time is:

$$ O\big((|V| + |E|) \log |V|\big) $$

Diagrams

flowchart TD
    Start([Start]) --> Init[Set dist=0 for source, infinity for others]
    Init --> Loop{Any unvisited vertex left?}
    Loop -- No --> End([Done])
    Loop -- Yes --> Pick[Pick unvisited vertex with min distance]
    Pick --> Relax[Relax all its neighbors]
    Relax --> Mark[Mark vertex as visited]
    Mark --> Loop

Pseudocode

function Dijkstra(Graph, source):
    for each vertex v in Graph:
        dist[v] = infinity
        prev[v] = undefined
    dist[source] = 0
    Q = set of all vertices in Graph  // priority queue keyed by dist

    while Q is not empty:
        u = vertex in Q with smallest dist[u]
        remove u from Q

        for each neighbor v of u still in Q:
            alt = dist[u] + weight(u, v)
            if alt

Step-by-Step Example

I’ll use the small graph shown in the diagram above, with source vertex A.

Final shortest distances from A: B=3, C=1, D=4, E=7.

Time Complexity

Best, average, and worst case are effectively the same order because the algorithm always processes every vertex and edge once, regardless of input arrangement.

Space Complexity

I need arrays for distance, previous-vertex tracking, and a visited flag, each of size $O(V)$, plus the priority queue which can hold up to $O(V)$ entries and the adjacency list which takes $O(V+E)$. Overall space is $O(V+E)$.

Correctness Analysis

The correctness proof I find most convincing is by induction on the order in which vertices are settled. The claim is: when a vertex $u$ is removed from the priority queue (settled), $dist[u]$ equals the true shortest distance $\delta(s,u)$. This holds because any path to $u$ that is shorter than $dist[u]$ would have to pass through some unvisited vertex $x$ with $dist[x] \geq dist[u]$ — but since all weights are non-negative, extending that path further can only add more cost, so it can never beat $dist[u]$. This is precisely why the non-negative weight condition is essential to the proof.

Advantages

Disadvantages

Applications

Implementation in C

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

#define V 5  // number of vertices

// Find the unvisited vertex with the minimum distance
int minDistance(int dist[], bool visited[]) {
    int min = INT_MAX, minIndex = -1;
    for (int v = 0; v  V; v++) {
        if (!visited[v] && dist[v]  min) {
            min = dist[v];
            minIndex = v;
        }
    }
    return minIndex;
}

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

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

    for (int count = 0; count  V - 1; count++) {
        int u = minDistance(dist, visited);
        if (u == -1) break;  // remaining vertices unreachable
        visited[u] = true;

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

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

int main() {
    // 0=A, 1=B, 2=C, 3=D, 4=E
    int graph[V][V] = {
        {0, 4, 1, 0, 0},
        {4, 0, 2, 1, 0},
        {1, 2, 0, 5, 0},
        {0, 1, 5, 0, 3},
        {0, 0, 0, 3, 0}
    };

    dijkstra(graph, 0);
    return 0;
}

Sample Input and Output

Input: the adjacency matrix in the code above, source vertex A (index 0).

Output:

Vertex   Distance from Source
0        0
1        3
2        1
3        4
4        7

This matches the manual walkthrough I did earlier.

Optimization Techniques

Common Mistakes

Further Reading

Exit mobile version