Chapter 55 of 65

Dijkstra's Algorithm

On this page

Imagine you are using a map app to travel from your home to your college.

There are many possible routes. Some have fewer turns, some pass through more junctions, but what you really care about is the total distance (or total travel time).

A route with 3 roads of 2 km each (6 km total) is better than a route with 1 road of 10 km.

In the BFS chapter, we learned how to find the path with the fewest edges. But when roads have different lengths, the fewest edges is not always the shortest distance.

This is exactly the problem that Dijkstra's Algorithm solves.

Dijkstra's Algorithm finds the shortest distance from one source vertex to every other vertex in a weighted graph where all edge weights are non-negative.

It was designed by the Dutch computer scientist Edsger W. Dijkstra in 1956 (and published in 1959), and it is still one of the most frequently asked graph algorithms in coding interviews and placement tests.


Why BFS Is Not Enough

Consider this weighted graph:

        10
   A ────────── C
   │            │
 2 │            │ 1
   │            │
   B ────────── D
         3

Suppose we want to go from A to C.

BFS counts edges, so it picks:

A → C        (1 edge,  cost 10)

But the cheaper route is:

A → B → D → C   (3 edges, cost 2 + 3 + 1 = 6)

So:

Unweighted graph (all edges equal) → BFS
Weighted graph, non-negative edges  → Dijkstra

Single-Source Shortest Path

Dijkstra's algorithm solves the single-source shortest path problem.

Single-source shortest path: given one starting vertex (the source), find the minimum total weight needed to reach every other vertex.

The output is usually a dist[] array:

dist[v] = length of the shortest path from source to v

If a vertex cannot be reached at all, its distance stays infinity.


The Core Idea

Dijkstra's algorithm keeps a tentative distance for every vertex.

At the start:

dist[source] = 0
dist[every other vertex] = ∞

Then it repeats one simple step:

Pick the unvisited vertex with the smallest tentative distance, mark it as final, and use it to improve the distances of its neighbors.

Why can we mark it as final?

Because all edge weights are non-negative. If the closest unvisited vertex is at distance d, any other route to it would have to pass through some other unvisited vertex that is already at distance ≥ d, and adding more non-negative edges can never make it smaller than d.

This "always pick the closest one" choice makes Dijkstra a greedy algorithm.


Relaxation

The operation that "improves" a neighbor's distance is called relaxation. It is the heart of every shortest-path algorithm.

Relaxing an edge u → v with weight w means: if going through u gives a shorter path to v, update dist[v].

if dist[u] + w < dist[v]:
    dist[v] = dist[u] + w
    parent[v] = u

Example:

dist[u] = 3
w       = 2
dist[v] = 9

3 + 2 = 5 < 9  →  dist[v] becomes 5

If dist[u] + w is not smaller, nothing changes.

The parent[] array remembers which vertex we came from, so we can rebuild the actual path later.


Dijkstra Step by Step

Let's run Dijkstra on this undirected graph with source 0:

          4
     0 ─────── 1
     │       / │
   1 │    2/   │ 1
     │   /     │
     2 ─────── 3 ─────── 4
          5         3

Edges:

0 - 1 : 4
0 - 2 : 1
2 - 1 : 2
1 - 3 : 1
2 - 3 : 5
3 - 4 : 3

We use a min priority queue that stores pairs (node, distance) and always gives us the pair with the smallest distance.

Start

dist = [0, ∞, ∞, ∞, ∞]
PQ   = (0,0)

Step 1: Pop (0, 0)

Mark 0 as visited. Relax its edges:

0 → 1 : 0 + 4 = 4 < ∞   → dist[1] = 4
0 → 2 : 0 + 1 = 1 < ∞   → dist[2] = 1

dist = [0, 4, 1, ∞, ∞]
PQ   = (2,1) (1,4)

Step 2: Pop (2, 1)

Node 2 is the closest unvisited node. Mark it visited.

2 → 1 : 1 + 2 = 3 < 4   → dist[1] = 3
2 → 3 : 1 + 5 = 6 < ∞   → dist[3] = 6

dist = [0, 3, 1, 6, ∞]
PQ   = (1,3) (1,4) (3,6)

Notice that (1,4) is still in the queue even though we found a better distance for node 1. Java's PriorityQueue has no efficient "decrease key" operation, so we simply add a new pair and ignore the old one later.

Step 3: Pop (1, 3)

Mark 1 visited.

1 → 3 : 3 + 1 = 4 < 6   → dist[3] = 4

dist = [0, 3, 1, 4, ∞]
PQ   = (1,4) (3,4) (3,6)

Step 4: Pop (1, 4)

Node 1 is already visited, so this is a stale entry. Skip it.

Step 5: Pop (3, 4)

Mark 3 visited.

3 → 4 : 4 + 3 = 7 < ∞   → dist[4] = 7

dist = [0, 3, 1, 4, 7]
PQ   = (3,6) (4,7)

Step 6: Pop (3, 6)

Stale entry. Skip.

Step 7: Pop (4, 7)

Mark 4 visited. It has no unvisited neighbors. The queue is now empty.

Final answer:

Node:      0   1   2   3   4
Distance:  0   3   1   4   7

(When two pairs have the same distance, such as (1,4) and (3,4), the priority queue may return either one first. The final distances are the same either way.)


The Algorithm

Dijkstra(source):

    dist[all] = ∞
    dist[source] = 0
    add (source, 0) to min priority queue

    while priority queue is not empty:

        (u, d) = remove the pair with smallest d

        if u is already visited:
            continue            // stale entry

        mark u as visited

        for each edge (u → v, weight w):

            if v is not visited and dist[u] + w < dist[v]:

                dist[v] = dist[u] + w
                parent[v] = u
                add (v, dist[v]) to priority queue

Representing a Weighted Graph in Java

In the Graph Representation chapter, we stored a weighted adjacency list using a small Edge class with a destination and a weight. That works perfectly here too.

In competitive programming and interviews, a shorter alternative is common: store each edge as an int[] of size 2.

// edge = {neighbor, weight}
ArrayList<ArrayList<int[]>> graph = new ArrayList<>();

Adding an undirected edge u - v with weight w:

graph.get(u).add(new int[]{v, w});
graph.get(v).add(new int[]{u, w});

For a directed edge, add only the first line.


Dijkstra in Java

Here is a complete program for the graph we traced above. We add one extra vertex 5 with no edges to show how unreachable vertices are handled, and we also print the actual shortest path using parent[].

import java.util.ArrayList;
import java.util.Arrays;
import java.util.PriorityQueue;

class Main {

    static final int INF = Integer.MAX_VALUE;

    static void addEdge(
        ArrayList<ArrayList<int[]>> graph,
        int u,
        int v,
        int w
    ) {

        graph.get(u).add(new int[]{v, w});
        graph.get(v).add(new int[]{u, w});
    }

    static int[] dijkstra(
        int source,
        ArrayList<ArrayList<int[]>> graph,
        int[] parent
    ) {

        int n = graph.size();

        int[] dist = new int[n];
        Arrays.fill(dist, INF);
        Arrays.fill(parent, -1);

        boolean[] visited = new boolean[n];

        // Each entry is {node, distance}
        PriorityQueue<int[]> pq =
            new PriorityQueue<>((a, b) -> Integer.compare(a[1], b[1]));

        dist[source] = 0;
        pq.add(new int[]{source, 0});

        while (!pq.isEmpty()) {

            int[] top = pq.poll();
            int u = top[0];

            if (visited[u]) {
                continue;   // stale entry, u is already final
            }

            visited[u] = true;

            for (int[] edge : graph.get(u)) {

                int v = edge[0];
                int w = edge[1];

                if (!visited[v] && dist[u] + w < dist[v]) {

                    dist[v] = dist[u] + w;
                    parent[v] = u;

                    pq.add(new int[]{v, dist[v]});
                }
            }
        }

        return dist;
    }

    static String path(int target, int[] parent) {

        ArrayList<Integer> nodes = new ArrayList<>();

        for (int v = target; v != -1; v = parent[v]) {
            nodes.add(0, v);
        }

        StringBuilder sb = new StringBuilder();

        for (int i = 0; i < nodes.size(); i++) {

            if (i > 0) {
                sb.append(" -> ");
            }

            sb.append(nodes.get(i));
        }

        return sb.toString();
    }

    public static void main(String[] args) {

        int vertices = 6;

        ArrayList<ArrayList<int[]>> graph = new ArrayList<>();

        for (int i = 0; i < vertices; i++) {
            graph.add(new ArrayList<>());
        }

        addEdge(graph, 0, 1, 4);
        addEdge(graph, 0, 2, 1);
        addEdge(graph, 2, 1, 2);
        addEdge(graph, 1, 3, 1);
        addEdge(graph, 2, 3, 5);
        addEdge(graph, 3, 4, 3);

        // Vertex 5 has no edges, so it is unreachable

        int[] parent = new int[vertices];

        int[] dist = dijkstra(0, graph, parent);

        for (int v = 0; v < vertices; v++) {

            if (dist[v] == INF) {
                System.out.println("Node " + v + " : unreachable");
            } else {
                System.out.println(
                    "Node " + v + " : " + dist[v]
                    + "   path: " + path(v, parent)
                );
            }
        }
    }
}

Output:

Node 0 : 0   path: 0
Node 1 : 3   path: 0 -> 2 -> 1
Node 2 : 1   path: 0 -> 2
Node 3 : 4   path: 0 -> 2 -> 1 -> 3
Node 4 : 7   path: 0 -> 2 -> 1 -> 3 -> 4
Node 5 : unreachable

Understanding the Important Lines

The Min Priority Queue

PriorityQueue<int[]> pq =
    new PriorityQueue<>((a, b) -> Integer.compare(a[1], b[1]));

The comparator orders pairs by a[1], the distance. So poll() always returns the closest pair. We use Integer.compare instead of a[1] - b[1] because subtraction can overflow for very large values.

Skipping Stale Entries

if (visited[u]) {
    continue;
}

Because we add a new pair every time a distance improves, the same node can appear in the queue many times. Only the first time it is popped (with its smallest distance) matters.

Another common way to write the same check is:

int d = top[1];

if (d > dist[u]) {
    continue;   // this pair is outdated
}

Both versions work correctly for non-negative weights.

Rebuilding the Path

To get the path to 4, we follow parents backwards:

4 → parent 3 → parent 1 → parent 2 → parent 0 → parent -1 (stop)

Reverse it: 0 → 2 → 1 → 3 → 4

Time and Space Complexity

With an adjacency list and a binary-heap priority queue (Java's PriorityQueue):

  • Every edge can cause at most one push into the queue, so the queue holds at most O(E) entries.

  • Each push and pop costs O(log E), and log E ≤ log V² = 2 log V, so this is the same as O(log V).

Time  → O((V + E) log V)
Space → O(V + E)

You will often see this written as O(E log V), which is the same thing for a connected graph.

The O(V²) Version for Dense Graphs

Dijkstra can also be written without a priority queue. In each round, we simply scan all vertices to find the closest unvisited one.

import java.util.Arrays;

class Main {

    static final int INF = Integer.MAX_VALUE;

    // O(V^2) Dijkstra using an adjacency matrix (0 = no edge)
    static int[] dijkstra(int source, int[][] matrix) {

        int n = matrix.length;

        int[] dist = new int[n];
        Arrays.fill(dist, INF);

        boolean[] visited = new boolean[n];

        dist[source] = 0;

        for (int round = 0; round < n; round++) {

            // 1. Pick the unvisited node with the smallest distance
            int u = -1;

            for (int i = 0; i < n; i++) {
                if (!visited[i] && (u == -1 || dist[i] < dist[u])) {
                    u = i;
                }
            }

            if (dist[u] == INF) {
                break;   // remaining nodes are unreachable
            }

            visited[u] = true;

            // 2. Relax all edges going out of u
            for (int v = 0; v < n; v++) {

                if (matrix[u][v] != 0 && !visited[v]
                        && dist[u] + matrix[u][v] < dist[v]) {

                    dist[v] = dist[u] + matrix[u][v];
                }
            }
        }

        return dist;
    }

    public static void main(String[] args) {

        int[][] matrix = {
            {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}
        };

        System.out.println(Arrays.toString(dijkstra(0, matrix)));
    }
}

Output:

[0, 3, 1, 4, 7]

This version runs in O(V²) time. (Using 0 to mean "no edge" only works here because this example has no zero-weight edges.)

Version

Time

Best for

Priority queue + adjacency list

O((V + E) log V)

Sparse graphs (most interview problems)

Simple array scan + matrix

O(V²)

Very dense graphs where E is close to V²


Why Dijkstra Fails with Negative Edges

Dijkstra's key assumption is: once a vertex is popped, its distance is final. Negative edges break this assumption.

Consider this directed graph:

0 → 1 : 2
0 → 2 : 5
2 → 1 : -4
1 → 3 : 1

The true shortest distances are:

dist[1] = 0 → 2 → 1     = 5 + (-4) = 1
dist[3] = 0 → 2 → 1 → 3 = 1 + 1    = 2

But Dijkstra pops node 1 first (distance 2 is smaller than 5), marks it final, and uses it to set dist[3] = 3. When it later discovers the cheaper route through 2, node 1 is already visited.

Running our dijkstra() function on this directed graph returns:

dist = [0, 2, 5, 3]

The correct answer is [0, 1, 5, 2], so Dijkstra gave two wrong distances.

Never use Dijkstra's algorithm when the graph has negative edge weights. Use Bellman-Ford instead, which we study in the next chapter.

Zero-weight edges are fine. Only negative weights cause problems.


Directed and Undirected Graphs

Dijkstra works on both. The only difference is how you build the adjacency list:

Undirected: add u → v AND v → u
Directed:   add only u → v

One subtle point: in an undirected graph, a single negative edge u - v already behaves like a negative cycle (you can go back and forth forever), so shortest paths are not even well defined.


Dijkstra on a Grid

Many interview problems hide a graph inside a 2D grid. Each cell is a vertex, and moving to a neighboring cell has a cost.

For example, "minimum cost path where each cell has a cost to enter":

1  3  1
1  5  1
4  2  1

If you can move in all four directions, this is just Dijkstra where the priority queue stores {row, col, cost}. The cheapest path from top-left to bottom-right is:

1 → 3 → 1 → 1 → 1   total = 7

The pattern is exactly the same: pop the cheapest cell, skip it if already visited, relax its 4 neighbors.


Common Mistakes

1. Using Dijkstra with Negative Weights

As we saw, the answer can silently be wrong. Check the constraints before choosing the algorithm.

2. Integer Overflow

If you compute dist[u] + w while dist[u] is Integer.MAX_VALUE, the result wraps around to a large negative number. In the priority-queue version this cannot happen, because a node is popped only after it has received a real distance. But in other variations, always check dist[u] != INF first. If path sums can exceed about 2.1 billion, use long.

3. Using a Max Heap by Mistake

Java's PriorityQueue is a min heap by default, but if you write a wrong comparator (for example b[1] - a[1]), you get the farthest node first and the algorithm breaks.

4. Forgetting to Skip Stale Entries

Without the visited (or d > dist[u]) check, a node may be processed many times. The answer is still correct for non-negative weights, but the algorithm does a lot of unnecessary extra work.

5. Using BFS for Weighted Graphs

BFS minimizes the number of edges, not the total weight.

6. Marking Visited When Pushing

In BFS, we mark a node visited when we add it to the queue. In Dijkstra, we mark it visited only when we pop it, because a better distance may still be found before then.


Dijkstra vs BFS vs Other Algorithms

Algorithm

Graph type

Negative edges?

Time

BFS

Unweighted

Not applicable

O(V + E)

Dijkstra

Weighted, single source

No

O((V + E) log V)

Bellman-Ford

Weighted, single source

Yes (detects negative cycles)

O(V · E)

Floyd-Warshall

Weighted, all pairs

Yes (no negative cycles)

O(V³)

We cover Bellman-Ford and Floyd-Warshall in the next chapter.

Dijkstra vs Prim

Dijkstra looks very similar to Prim's algorithm from the Minimum Spanning Tree chapter. Both use a min priority queue. The difference is the key stored in the queue:

Prim:     key = weight of the single edge connecting v to the tree
Dijkstra: key = total distance from the source to v

So Prim builds the cheapest tree connecting all vertices, while Dijkstra builds the tree of shortest paths from one source. They are usually different trees.


Real-Life Applications

  • Maps and navigation: shortest route by distance or time (real systems use faster variants such as A* built on the same idea).

  • Network routing: link-state routing protocols like OSPF use Dijkstra's shortest path first (SPF) algorithm.

  • Games: finding the cheapest path for a character on a weighted map.

  • Flight booking: cheapest route between two cities.


Interview Tips and Practice Problems

Look for these signals in a problem:

"minimum cost / minimum time / shortest distance"
+ edges or moves with DIFFERENT non-negative costs
→ Dijkstra

Good problems to practice:

  1. Network Delay Time (LeetCode 743)

  2. Path With Minimum Effort (LeetCode 1631)

  3. Cheapest Flights Within K Stops (LeetCode 787) – a twist with a limit on stops

  4. Path with Maximum Probability (LeetCode 1514)

  5. Swim in Rising Water (LeetCode 778)

  6. Number of Ways to Arrive at Destination (LeetCode 1976)


The Main Idea

Dijkstra's Algorithm finds the shortest distance from one source to every other vertex in a graph with non-negative edge weights.

The process is:

dist[source] = 0, others = ∞
        ↓
Pop the closest unvisited vertex
        ↓
Mark it final (visited)
        ↓
Relax all its edges
        ↓
Push improved distances into the priority queue
        ↓
Repeat until the queue is empty

The key relationship is:

Dijkstra
   ↓
Min Priority Queue
   ↓
Greedy: always expand the closest vertex

Its complexity with a binary heap is:

Time  → O((V + E) log V)
Space → O(V + E)

Remember these four things:

1. Dijkstra uses a min priority queue.
2. Relaxation: if dist[u] + w < dist[v], update dist[v].
3. A vertex is final when it is popped, not when it is pushed.
4. Dijkstra does NOT work with negative edge weights.

If a problem asks for the minimum total cost in a graph where costs are different but never negative, Dijkstra should be your first choice.