How to Implement Dijkstra's Algorithm for Shortest Paths in Weighted Graphs

Dijkstra's algorithm finds the shortest path from a source node to all other nodes in a weighted graph by using a priority queue to greedily expand the closest unvisited vertex first.

The labuladong/fucking-algorithm repository provides a comprehensive, production-ready implementation of Dijkstra's algorithm in its Data Structure Series. The article explains how to implement Dijkstra's algorithm for shortest paths by treating it as an enhanced version of breadth-first search (BFS) that handles weighted edges through two critical modifications.

Understanding Dijkstra's Algorithm as Priority Queue BFS

Traditional BFS works for unweighted graphs because each edge contributes equally to the path length. In weighted graphs, edges have varying costs, so a simple FIFO queue cannot guarantee that the first path found is the shortest. The solution is to upgrade the queue to order nodes by their current distance from the source.

The Priority Queue Mechanism

Instead of a standard queue, Dijkstra's algorithm uses a priority queue (min-heap) ordered by distFromStart — the accumulated weight from the source node to the current node. This greedy ordering ensures that when a node is removed from the queue, its distance is finalized and optimal. According to the source code in 数据结构系列/dijkstra算法.md, this approach yields a time complexity of O(E log V) (or O(E log E) depending on the heap implementation), where E is the number of edges and V is the number of vertices.

Distance Memoization with distTo Array

The algorithm maintains a distTo array (or DP table) that records the best-known distance to each vertex. When processing a node, the algorithm checks if the extracted distance matches the recorded distance in distTo. If the extracted distance is larger, the entry is considered stale and is discarded. This technique eliminates the need for an explicit visited set while preventing infinite loops and redundant processing.

Complete Java Implementation from labuladong/fucking-algorithm

The repository provides a complete reference implementation in Java. The solution uses an auxiliary State class to encapsulate node identifiers and their distances for the priority queue.

The State Class

// State class used by the priority queue
class State {
    int id;               // graph node identifier
    int distFromStart;    // current shortest distance from the source
    State(int id, int dist) { 
        this.id = id; 
        this.distFromStart = dist; 
    }
}

Full Algorithm Implementation

The following implementation returns an array containing the shortest distance from the start node to every other vertex in the graph:

// Dijkstra implementation that returns distances from `start` to all vertices
int[] dijkstra(int start, Graph graph) {
    int V = graph.size();
    int[] distTo = new int[V];
    Arrays.fill(distTo, Integer.MAX_VALUE);
    distTo[start] = 0;

    Queue<State> pq = new PriorityQueue<>(
        (a, b) -> a.distFromStart - b.distFromStart);

    pq.offer(new State(start, 0));

    while (!pq.isEmpty()) {
        State cur = pq.poll();
        int u = cur.id;
        int d = cur.distFromStart;

        // discard stale entries
        if (d > distTo[u]) continue;

        for (int v : graph.neighbors(u)) {
            int nd = distTo[u] + graph.weight(u, v);
            if (nd < distTo[v]) {
                distTo[v] = nd;
                pq.offer(new State(v, nd));
            }
        }
    }
    return distTo;
}

This code is adapted from the source file 数据结构系列/dijkstra算法.md in the labuladong/fucking-algorithm repository.

Single-Target Optimization with Early Exit

When you only need the shortest path to a specific destination rather than all vertices, you can optimize the algorithm to exit early. As soon as the target node is extracted from the priority queue, its distance is guaranteed to be optimal, allowing immediate termination.

// Variant that stops as soon as the destination `end` is reached
int dijkstra(int start, int end, Graph graph) {
    int V = graph.size();
    int[] distTo = new int[V];
    Arrays.fill(distTo, Integer.MAX_VALUE);
    distTo[start] = 0;

    Queue<State> pq = new PriorityQueue<>(
        (a, b) -> a.distFromStart - b.distFromStart);
    pq.offer(new State(start, 0));

    while (!pq.isEmpty()) {
        State cur = pq.poll();
        int u = cur.id;
        int d = cur.distFromStart;

        if (u == end) return d;               // early exit
        if (d > distTo[u]) continue;

        for (int v : graph.neighbors(u)) {
            int nd = distTo[u] + graph.weight(u, v);
            if (nd < distTo[v]) {
                distTo[v] = nd;
                pq.offer(new State(v, nd));
            }
        }
    }
    return Integer.MAX_VALUE; // unreachable
}

Use this variant when computing paths between specific pairs of nodes to reduce unnecessary computation, particularly in large sparse graphs.

Key Files in the Repository

The labuladong/fucking-algorithm repository organizes its Dijkstra implementation across several related files:

• 数据结构系列/dijkstra算法.md — Contains the complete theoretical explanation, complexity analysis, and Java reference implementation discussed in this article.
• 数据结构系列/图.md — Provides foundational graph theory concepts, including adjacency list representations and related algorithms like BFS and topological sort that contextualize Dijkstra's approach.
• 算法思维系列/学习数据结构和算法的高效方法.md — Explains the "BFS with priority queue" mental model that underlies the implementation strategy.

Summary

• Dijkstra's algorithm computes shortest paths in weighted graphs by greedily expanding the closest node using a priority queue.
• The priority queue orders nodes by distFromStart, ensuring O(E log V) time complexity.
• The distTo array memoizes best-known distances and filters stale queue entries, eliminating the need for a separate visited set.
• The labuladong/fucking-algorithm repository provides complete Java implementations in 数据结构系列/dijkstra算法.md for both all-vertices and single-target scenarios.

Frequently Asked Questions

What is the time complexity of Dijkstra's algorithm with a priority queue?

When implemented with a binary heap priority queue, Dijkstra's algorithm runs in O(E log V) time, where E is the number of edges and V is the number of vertices. Each node is extracted from the heap once (O(log V) per extraction), and each edge may trigger a decrease-key operation (also O(log V)). According to the labuladong/fucking-algorithm implementation, using Java's PriorityQueue yields O(E log E) in the worst case due to duplicate entries, though this does not affect the asymptotic bound for dense graphs.

Why does Dijkstra's algorithm fail with negative edge weights?

Dijkstra's algorithm relies on the greedy property that once a node is extracted from the priority queue, its shortest distance is finalized. With negative edge weights, a later path through a different node could reduce the distance to an already-processed vertex, violating this assumption. The labuladong/fucking-algorithm article notes that for graphs with negative weights, the Bellman-Ford algorithm or SPFA should be used instead, as they allow for distance relaxation across multiple iterations.

How does the early exit optimization work in single-target Dijkstra?

The early exit variant terminates execution as soon as the destination node is extracted from the priority queue. Because the priority queue always extracts the node with the smallest known distance, the first time the target node is removed, its distance is guaranteed to be the global shortest path. The labuladong/fucking-algorithm implementation checks if (u == end) return d; immediately after polling from the queue, significantly improving performance when only a specific path is needed rather than the full distance matrix.

What is the purpose of the distTo array in the implementation?

The distTo array serves as a memoization table that tracks the best-known shortest distance to each vertex discovered so far. It enables the algorithm to detect stale entries in the priority queue—when a node is extracted with a distance greater than its recorded distTo value, the entry is discarded because a better path has already been found. According to the source code in 数据结构系列/dijkstra算法.md, this technique eliminates the need for an explicit visited set while preventing redundant processing and infinite loops.

{
  "mcpServers": {
    "instagit": {
      "command": "npx",
      "args": ["-y", "instagit@latest"]
    }
  }
}