Offensive Security Researcher & Quantum Cryptography Analyst

Dijkstra’s Algorithm: Working, Explanation, and Shortest Path Finding

Abdul Wahab Junaid
dijkstra's algorithm and working of this algorithm

Of all the shortest path algorithms I’ve studied, Dijkstra’s algorithm is the one I reach for most often, simply because so many real-world graphs — road networks, network routing tables, dependency graphs with non-negative costs — fit its core assumption of non-negative edge weights. It finds the shortest path from a single source vertex to every other vertex in a weighted graph, and it does so by always greedily expanding the closest unvisited vertex first. I find its greedy strategy satisfying precisely because it’s provably correct under the right conditions, and understanding why it works, and where it breaks down (negative weights), has taught me a lot about the boundaries of greedy algorithms in general.

History and Background

I credit this algorithm to Edsger W. Dijkstra, a Dutch computer scientist who conceived of it in 1956 and published it in 1959 in a short paper titled “A note on two problems in connexion with graphs.” What I find charming about the origin story, which Dijkstra himself recounted later in life, is that he designed the algorithm in about twenty minutes while sitting in a café in Amsterdam with his fiancée, thinking about how to demonstrate the capabilities of a new computer, the ARMAC, by solving a practical problem: finding the shortest route between two cities in the Netherlands. He didn’t have paper at the time, so he worked it out mentally, and it later became one of the most widely taught and used algorithms in computer science.

Problem Statement

I want to find the shortest path from a single source vertex to every other vertex in a weighted graph where all edge weights are non-negative. If negative weights are present, Dijkstra’s greedy strategy can produce incorrect results, since it assumes that once a vertex’s shortest distance has been finalized, no future relaxation could ever improve it — an assumption that breaks down when negative edges allow a “cheaper” path to be discovered later. Given this restriction, Dijkstra’s algorithm solves the single-source shortest path problem efficiently, typically much faster than the more general Bellman-Ford algorithm when the non-negative weight condition holds.

Core Concepts

How It Works

I proceed as follows:

  1. I initialize the distance to the source as 0, and to every other vertex as infinity, and I place all vertices into a priority queue keyed by their tentative distance.
  2. I repeatedly extract the vertex u with the smallest tentative distance from the priority queue.
  3. I mark u as finalized (visited) — its distance is now guaranteed correct.
  4. For every neighbor v of u connected by an edge of weight w, I check if dist[u] + w ; if so, I update dist[v] and adjust its position in the priority queue.
  5. I repeat steps 2-4 until the priority queue is empty (or until I’ve finalized the specific destination I care about, if I only need a single target).

Working Principle

The mechanism rests on a greedy assumption that turns out to be provably valid whenever all edge weights are non-negative: the unvisited vertex with the smallest current tentative distance cannot possibly be improved later. This is because any alternative path to that vertex would have to go through some other unvisited vertex, but since all unvisited vertices currently have tentative distances greater than or equal to the one I’m about to finalize, and since edge weights are non-negative, any such alternative path could only be equal to or longer than the direct path already found. This is precisely the property that fails when negative weights are allowed — a currently “longer” path through an unvisited vertex could, with a negative edge, end up shorter than what was just finalized, which is why Dijkstra’s algorithm cannot handle negative weights correctly.

Mathematical Foundation

I formalize the greedy choice property as follows. Let S be the set of finalized vertices at some point during execution, and let u be the unvisited vertex with the minimum tentative distance dist[u]. I claim dist[u] is the true shortest distance from the source s to u. Suppose, for contradiction, that some shorter path P from s to u exists. Since s \in S and u \notin S, path P must cross from S to the outside of S at some edge (x, y), where x \in S and y \notin S. Because edge weights are non-negative:

$$ dist[y] \leq \text{length of the portion of } P \text{ from } s \text{ to } y \leq \text{length of } P

But this contradicts the choice of u as the vertex with minimum tentative distance among unvisited vertices, since y would then have a smaller tentative distance than u. Therefore no shorter path P can exist, proving dist[u] is already correct.

Using a binary heap-based priority queue, the total time complexity is:

$$ T(|V|, |E|) = O\big((|V| + |E|) \log |V|\big) $$

which, with a Fibonacci heap, can be improved to O(|E| + |V| \log |V|).

Diagrams

flowchart TD
    A["Initialize dist[source]=0, all others=infinity; add all to priority queue"] --> B{Priority queue empty?}
    B -- Yes --> H[All shortest distances finalized]
    B -- No --> C["Extract vertex u with minimum tentative distance"]
    C --> D[Mark u as finalized]
    D --> E["For each neighbor v of u with edge weight w"]
    E --> F{"dist[u] + w  G["dist[v] = dist[u] + w; update priority queue"]
    F -- No --> B
    G --> B

Pseudocode

function dijkstra(graph, source, V):
    dist = array of size V, initialized to infinity
    dist[source] = 0
    visited = set of size V, all false
    priorityQueue = min-heap keyed by dist, initially containing (0, source)

    while priorityQueue is not empty:
        (d, u) = priorityQueue.extractMin()
        if visited[u]:
            continue
        visited[u] = true

        for each neighbor v of u with edge weight w:
            if not visited[v] and dist[u] + w

Step-by-Step Example

Consider a graph with vertices S, A, B, C and edges: S->A (2), S->B (6), A->B (3), A->C (8), B->C (1), source S.

Initialization: dist = {S: 0, A: ∞, B: ∞, C: ∞}, priority queue = [(0, S)].

Step 1: Extract S (distance 0). Relax neighbors: dist[A] = min(∞, 0+2) = 2; dist[B] = min(∞, 0+6) = 6. Queue now has [(2, A), (6, B)].

Step 2: Extract A (distance 2, the smallest). Finalize A. Relax neighbors: dist[B] = min(6, 2+3) = 5; dist[C] = min(∞, 2+8) = 10. Queue now has [(5, B), (6, B) stale, (10, C)].

Step 3: Extract B (distance 5, the smallest valid entry). Finalize B. Relax neighbors: dist[C] = min(10, 5+1) = 6. Queue now has [(6, B) stale, (6, C), (10, C) stale].

Step 4: Extract the stale (6, B) entry, skip since B is already visited. Extract (6, C). Finalize C.

Final distances: S: 0, A: 2, B: 5, C: 6

Time Complexity

Space Complexity

Dijkstra’s algorithm requires O(|V|) space for the distance array and the visited/finalized set, plus O(|V|) space for the priority queue (which may temporarily hold up to O(|E|) entries if stale entries aren’t removed eagerly, though this doesn’t change the asymptotic space complexity given typical heap implementations). The graph itself, using an adjacency list, requires O(|V| + |E|) space.

Correctness Analysis

The correctness proof follows directly from the greedy choice property I derived in the Mathematical Foundation section: at every step, the unvisited vertex with the smallest tentative distance is guaranteed to have already reached its true shortest distance, given non-negative edge weights. I prove this by strong induction on the order in which vertices are finalized: the base case is the source itself, finalized at distance 0, which is trivially correct. For the inductive step, assuming every previously finalized vertex has a correct shortest distance, the contradiction argument shown earlier proves that the next vertex extracted from the priority queue must also have a correct shortest distance, since any alternative shorter path would necessarily pass through an unvisited vertex with an even smaller (contradictory) tentative distance. By induction, every vertex is correctly finalized in the order it is extracted from the priority queue.

Advantages

Disadvantages

Applications

Implementation in C

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

#define V 4

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 source) {
    int dist[V];
    bool visited[V];

    for (int i = 0; i  V; i++) {
        dist[i] = INT_MAX;
        visited[i] = false;
    }
    dist[source] = 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] != 0 &&
                dist[u] != INT_MAX &&
                dist[u] + graph[u][v]  dist[v]) {
                dist[v] = dist[u] + graph[u][v];
            }
        }
    }

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

int main() {
    /* 0=S, 1=A, 2=B, 3=C. 0 means no direct edge. */
    int graph[V][V] = {
        {0, 2, 6, 0},
        {2, 0, 3, 8},
        {6, 3, 0, 1},
        {0, 8, 1, 0}
    };

    dijkstra(graph, 0);
    return 0;
}

Sample Input and Output

Input: graph with vertices S(0), A(1), B(2), C(3) and edges S-A(2), S-B(6), A-B(3), A-C(8), B-C(1), source S.

Output:

Vertex	Distance from Source
0	0
1	2
2	5
3	6

Optimization Techniques

Common Mistakes

Further Reading

Exit mobile version