Dijkstra's Algorithm

Category: Graphs

The problem

A graph with weighted edges doesn't have a single "distance" between two nodes the way a grid does — the cheapest path might have more hops than a more expensive one. Brute-forcing every path between a source and every other node is combinatorially hopeless past a handful of nodes. What's needed is a way to build up the true shortest distance to every node incrementally, without ever re-examining a node once its shortest distance is known for certain.

The solution

Greedily settle the closest not-yet-settled node on every step, then relax (potentially lower) the tentative distance of each of its neighbors through it. Because every edge weight is non-negative, once a node is settled — its shortest distance is fixed — nothing settled later could ever offer it a cheaper path, since any such path would have to go through a node that's farther away than it already is. That single guarantee is the entire correctness argument, and it's also exactly why this algorithm breaks the moment a negative edge weight is allowed.

flowchart LR
    A((A)) -- 1 --> B((B))
    A -- 4 --> C((C))
    B -- 1 --> C
    B -- 5 --> D((D))
    C -- 1 --> D
    A -. 10 .-> D

Classic example

classic/WeightedGraph is an undirected, non-negative-weight graph stored as a hand-rolled adjacency list, carrying shortestPathFrom(source) — Dijkstra's algorithm — as its core operation. The frontier is a plain java.util.PriorityQueue, a deliberate, documented exception to this repo's usual "no java.util shortcut" rule: the data structure this module showcases is the graph algorithm itself — Dijkstra's greedy relaxation strategy — not heap mechanics, which is its own separate structure with its own (future) dedicated module in this repo's roadmap. WeightedGraphTest covers an isolated unreachable node, a node whose shortest distance has to be relaxed downward more than once (forcing the algorithm to skip a stale, already-settled queue entry), and a worse alternate path that must not overwrite an already-better known distance.

Applied example: interbank settlement routing

applied/InterbankSettlementRouter routes a settlement across correspondent-bank rails — PIX, TED, and Boleto-style hops, each carrying its own fee — instead of assuming a single fixed path or the fewest hops. Moving funds from a source account to a destination rarely happens over one direct rail: it hops through intermediate correspondent accounts, and the cheapest chain of hops isn't always the one with the fewest hops or the cheapest first step. Modeling every known rail as a weighted edge and running Dijkstra from the source account finds the minimum-total-fee route in one pass. InterbankSettlementRouterTest covers a case where a two-hop correspondent route beats a more expensive direct rail, and a case where no known chain of rails reaches the destination at all.

Benchmark

./gradlew :graphs:dijkstra:jmh

Real run (JMH 1.37, JDK 26.0.2, 2 warmup + 3 measurement iterations, 1 fork). A random connected graph, edge density held at roughly 4 edges per node as node count scales up, so V and E grow together:

Cost grows noticeably faster than the node count alone (100x nodes -> ~536x slower), which tracks with what's actually being measured: both V and E scale together here (edge density held at ~4 per node), so the workload itself grows faster than V, and the lazy-deletion priority queue used here (no decrease-key; a relaxed node gets a fresh queue entry instead) means the queue can hold on the order of E entries rather than V, pushing the real constant closer to O(E log E) than the idealized O((V+E) log V). Either way, the shape is unmistakably far better-than-quadratic and worse-than-linear — exactly the "smarter than brute force, not free" territory this algorithm is supposed to occupy.

When not to use it

• Any edge weight can be negative? Dijkstra's greedy "once settled, never revisited" argument breaks immediately — Bellman-Ford (tolerates negative weights, detects negative cycles) is the correct tool instead, at a higher O(V·E) cost.
• Need the shortest path between every pair of nodes, not just from one source? Running this once per node costs O(V·(V+E) log V); an all-pairs algorithm like Floyd-Warshall (O(V^3), but with no per-run priority-queue overhead) usually wins once most pairs are needed anyway.
• Unweighted graph (every edge effectively costs the same)? A plain BFS finds the shortest path in O(V+E) with no priority queue needed at all — this repo's future Graph (BFS/DFS) module is the right fit for that narrower case.

Test coverage

100% instruction coverage, 100% branch coverage (JaCoCo). Reproduce it yourself:

./gradlew :graphs:dijkstra:jacocoTestReport

Report at graphs/dijkstra/build/reports/jacoco/test/html/index.html.

Unit tests

package com.datastructures.graphs.dijkstra.classic;

import org.junit.jupiter.api.Test;

import java.util.Map;

import static org.assertj.core.api.Assertions.assertThat;
import static org.assertj.core.api.Assertions.assertThatThrownBy;

class WeightedGraphTest {

    @Test
    void singleNodeGraphReachesOnlyItself() {
        WeightedGraph<String> graph = new WeightedGraph<>();
        graph.addNode("A");

        Map<String, Long> distances = graph.shortestPathFrom("A");

        assertThat(distances).containsExactly(Map.entry("A", 0L));
        assertThat(graph.nodeCount()).isEqualTo(1);
    }

    @Test
    void addEdgeRejectsANegativeWeight() {
        WeightedGraph<String> graph = new WeightedGraph<>();

        assertThatThrownBy(() -> graph.addEdge("A", "B", -1))
                .isInstanceOf(IllegalArgumentException.class)
                .hasMessageContaining("-1");
    }

    @Test
    void aNodeWithNoPathToTheSourceIsAbsentFromTheResult() {
        WeightedGraph<String> graph = new WeightedGraph<>();
        graph.addEdge("A", "B", 1);
        graph.addNode("Z"); // isolated: no edge connects it to anything

        Map<String, Long> distances = graph.shortestPathFrom("A");

        assertThat(distances).containsOnlyKeys("A", "B");
        assertThat(distances).doesNotContainKey("Z");
    }

    /**
     * A graph shaped so Dijkstra must relax B's and D's tentative distance downward more than
     * once (forcing multiple, decreasing queue entries for the same node — i.e. stale entries
     * that get skipped once the node is already settled) before settling on the true shortest
     * distances.
     */
    @Test
    void dijkstraFindsTheTrueShortestDistancesThroughRelaxationAndSkipsStaleQueueEntries() {
        WeightedGraph<String> graph = new WeightedGraph<>();
        graph.addEdge("A", "B", 1);
        graph.addEdge("A", "C", 4);
        graph.addEdge("B", "C", 1);
        graph.addEdge("C", "D", 1);
        graph.addEdge("B", "D", 5);
        graph.addEdge("A", "D", 10);

        Map<String, Long> distances = graph.shortestPathFrom("A");

        assertThat(distances)
                .containsEntry("A", 0L)
                .containsEntry("B", 1L)
                .containsEntry("C", 2L)
                .containsEntry("D", 3L);
    }

    /**
     * B is settled before C (distance 1 < 2), and B has a very expensive edge to C. That
     * relaxation attempt must be rejected because it's worse than C's already-known distance —
     * the "not an improvement" branch of the relaxation check.
     */
    @Test
    void aWorseAlternatePathDoesNotOverwriteAnAlreadyBetterKnownDistance() {
        WeightedGraph<String> graph = new WeightedGraph<>();
        graph.addEdge("A", "B", 1);
        graph.addEdge("A", "C", 2);
        graph.addEdge("B", "C", 100);

        Map<String, Long> distances = graph.shortestPathFrom("A");

        assertThat(distances).containsEntry("C", 2L);
    }
}

package com.datastructures.graphs.dijkstra.applied;

import org.junit.jupiter.api.Test;

import java.util.Optional;

import static org.assertj.core.api.Assertions.assertThat;

class InterbankSettlementRouterTest {

    private final BankAccount originAccount = new BankAccount("BANK-A", "0001");
    private final BankAccount correspondentAccount = new BankAccount("BANK-B", "0002");
    private final BankAccount destinationAccount = new BankAccount("BANK-C", "0003");
    private final BankAccount unreachableAccount = new BankAccount("BANK-Z", "9999");

    @Test
    void findsTheCheapestFeeAcrossACorrespondentBankHopEvenWhenADirectRailIsMoreExpensive() {
        InterbankSettlementRouter router = new InterbankSettlementRouter();
        router.registerRail(originAccount, destinationAccount, 900); // expensive direct PIX rail
        router.registerRail(originAccount, correspondentAccount, 100); // TED hop
        router.registerRail(correspondentAccount, destinationAccount, 150); // Boleto hop

        Optional<Long> cheapestFee = router.cheapestSettlementFee(originAccount, destinationAccount);

        assertThat(cheapestFee).contains(250L);
    }

    @Test
    void noKnownChainOfRailsReturnsAnEmptyResult() {
        InterbankSettlementRouter router = new InterbankSettlementRouter();
        router.registerRail(originAccount, correspondentAccount, 100);

        Optional<Long> cheapestFee = router.cheapestSettlementFee(originAccount, unreachableAccount);

        assertThat(cheapestFee).isEmpty();
    }
}

View full JaCoCo coverage report →