How Dijkstra's Algorithm Works — With a Complete Java Implementation

Every time you open Google Maps and ask for the fastest route from point A to point B, an algorithm invented in 1956 is running under the hood. That algorithm is Dijkstra’s algorithm, and despite its age, it remains one of the most elegant and widely used graph algorithms in computer science.

The Problem Dijkstra Solves

Given a graph with weighted edges, find the shortest path from a source node to every other node.

        A
      /   \
    4/     \2
    /       \
   B----3----C
   |       / |
  1|     /5  |6
   |   /     |
   D--E------F
      4

Shortest path from A to F?
  A → C → F = 2 + 6 = 8
  A → B → D → E → F = 4 + 1 + 4 + ??? (no direct edge)
  A → C → E → F = 2 + 5 + ??? (no edge from E to F)

Dijkstra's will tell you: A → C → F with cost 8.

When the graph is small, you can eyeball it. For a city with millions of intersections, you need an algorithm.

How Dijkstra’s Algorithm Works

Dijkstra is a greedy algorithm. At each step, it picks the unvisited node with the smallest known distance, marks it visited, and relaxes its neighbors — meaning it checks if going through the current node gives a shorter path to those neighbors.

The Core Idea in One Sentence

“The shortest path to any node is the minimum of (previously known distance, distance through current node + edge weight).”

The Step-by-Step Process

Let’s walk through it on this graph, starting from node A:

        A
      /   \
    4/     \2
    /       \
   B----3----C
   |       / |
  1|     /5  |6
   |   /     |
   D--E------F
      4

Step 1 — Initialize: Set the distance to the source node A as 0, and all other nodes as infinity. Mark all nodes as unvisited.

Distances:  A=0, B=∞, C=∞, D=∞, E=∞, F=∞

Step 2 — Pick the unvisited node with the smallest distance (A): Neighbors of A: B (weight 4) and C (weight 2). Relax them: is the current distance to B (∞) greater than distance to A (0) + edge weight (4)? Yes → set B = 4. Same for C → set C = 2.

Distances:  A=0, B=4, C=2, D=∞, E=∞, F=∞
Visited:    A

Step 3 — Pick unvisited node with smallest distance (C = 2): Neighbors of C: A (visited, ignore), B (weight 3), E (weight 5), F (weight 6). Relax B: is 4 > 2 + 3 = 5? No, keep B = 4. Relax E: set E = 2 + 5 = 7. Relax F: set F = 2 + 6 = 8.

Distances:  A=0, B=4, C=2, D=∞, E=7, F=8
Visited:    A, C

Step 4 — Pick unvisited node with smallest distance (B = 4): Neighbors of B: A (visited), C (visited), D (weight 1). Relax D: set D = 4 + 1 = 5.

Distances:  A=0, B=4, C=2, D=5, E=7, F=8
Visited:    A, C, B

Step 5 — Pick unvisited node with smallest distance (D = 5): Neighbors of D: B (visited), E (weight 4). Relax E: is 7 > 5 + 4 = 9? No, keep E = 7.

Distances:  A=0, B=4, C=2, D=5, E=7, F=8
Visited:    A, C, B, D

Step 6 — Pick unvisited node with smallest distance (E = 7): Neighbors of E: C (visited), D (visited), F — but there’s no direct edge from E to F in this graph, so nothing to relax.

Distances:  A=0, B=4, C=2, D=5, E=7, F=8
Visited:    A, C, B, D, E

Step 7 — Pick the last unvisited node (F = 8): No unvisited neighbors. Done.

Final distances:  A=0, B=4, C=2, D=5, E=7, F=8

The shortest path from A to F costs 8: A → C → F.

Why a Priority Queue?

The naive approach is scanning all unvisited nodes every iteration to find the minimum — O(V²) time. A min-heap PriorityQueue drops that to O((V + E) log V), which is dramatically faster for sparse graphs.

Instead of scanning every node to find the next minimum, just pop from the heap. When you update a distance, push the new (distance, node) pair onto the heap. The heap handles ordering for you.

Java Implementation

Here’s a complete, production-style implementation of Dijkstra’s algorithm in Java.

The Graph Representation

import java.util.*;

public class Graph {
    private final Map<String, List<Edge>> adjacencyList = new HashMap<>();

    public void addNode(String node) {
        adjacencyList.putIfAbsent(node, new ArrayList<>());
    }

    public void addEdge(String from, String to, int weight) {
        adjacencyList.get(from).add(new Edge(to, weight));
        // Remove the next line if your graph is directed
        adjacencyList.get(to).add(new Edge(from, weight));
    }

    public List<Edge> getNeighbors(String node) {
        return adjacencyList.getOrDefault(node, List.of());
    }

    public Set<String> getNodes() {
        return adjacencyList.keySet();
    }

    public record Edge(String target, int weight) {}
}

Dijkstra’s Algorithm

import java.util.*;

public class Dijkstra {

    public static Result shortestPath(Graph graph, String source) {
        Map<String, Integer> distances = new HashMap<>();
        Map<String, String> previous = new HashMap<>();
        Set<String> visited = new HashSet<>();

        // Initialize distances
        for (String node : graph.getNodes()) {
            distances.put(node, Integer.MAX_VALUE);
        }
        distances.put(source, 0);

        // Min-heap: (distance, node)
        PriorityQueue<NodeEntry> pq = new PriorityQueue<>();
        pq.add(new NodeEntry(source, 0));

        while (!pq.isEmpty()) {
            NodeEntry current = pq.poll();
            String currentNode = current.node();

            // Skip if we've already processed a better path to this node
            if (visited.contains(currentNode)) continue;
            visited.add(currentNode);

            for (Graph.Edge edge : graph.getNeighbors(currentNode)) {
                String neighbor = edge.target();

                if (visited.contains(neighbor)) continue;

                int newDistance = distances.get(currentNode) + edge.weight();

                if (newDistance < distances.get(neighbor)) {
                    distances.put(neighbor, newDistance);
                    previous.put(neighbor, currentNode);
                    pq.add(new NodeEntry(neighbor, newDistance));
                }
            }
        }

        return new Result(distances, previous);
    }

    public static List<String> reconstructPath(Map<String, String> previous, String target) {
        List<String> path = new LinkedList<>();
        String current = target;

        while (current != null) {
            path.addFirst(current);
            current = previous.get(current);
        }

        return path;
    }

    private record NodeEntry(String node, int distance)
        implements Comparable<NodeEntry> {
        @Override
        public int compareTo(NodeEntry other) {
            return Integer.compare(this.distance, other.distance);
        }
    }

    public record Result(Map<String, Integer> distances, Map<String, String> previous) {}
}

Running It

public class Main {
    public static void main(String[] args) {
        Graph graph = new Graph();

        graph.addNode("A");
        graph.addNode("B");
        graph.addNode("C");
        graph.addNode("D");
        graph.addNode("E");
        graph.addNode("F");

        graph.addEdge("A", "B", 4);
        graph.addEdge("A", "C", 2);
        graph.addEdge("B", "C", 3);
        graph.addEdge("B", "D", 1);
        graph.addEdge("C", "E", 5);
        graph.addEdge("C", "F", 6);
        graph.addEdge("D", "E", 4);

        Dijkstra.Result result = Dijkstra.shortestPath(graph, "A");

        System.out.println("Shortest distances from A:");
        for (String node : graph.getNodes()) {
            int distance = result.distances().get(node);
            String display = distance == Integer.MAX_VALUE ? "∞" : String.valueOf(distance);
            System.out.println("  A → " + node + ": " + display);
        }

        // Reconstruct path from A to F
        List<String> path = Dijkstra.reconstructPath(result.previous(), "F");
        System.out.println("\nPath from A to F: " + String.join(" → ", path));
        System.out.println("Total cost: " + result.distances().get("F"));
    }
}

Output:

Shortest distances from A:
  A → A: 0
  A → B: 4
  A → C: 2
  A → D: 5
  A → E: 7
  A → F: 8

Path from A to F: A → C → F
Total cost: 8

Time and Space Complexity

• V = number of vertices (nodes)
• E = number of edges

The PriorityQueue version (O((V + E) log V)) is the one you want. The V² version is only worth considering for dense graphs where E ≈ V², since the constant factors on a simple array scan can beat the heap’s overhead.

When Dijkstra Fails

Dijkstra has one critical limitation: it does not work with negative edge weights.

     A
   /   \
  4     -3
 /       \
B---------C
    2

Dijkstra would declare A → C = -3 and B = 4, then mark C visited.
It would miss the path A → C → B = -3 + 2 = -1, because C was already
"settled" before that better path through it was discovered.

If your graph has negative edges, use the Bellman-Ford algorithm instead — it’s slower (O(V × E)) but handles negatives and can detect negative cycles.

Where Dijkstra Is Used in the Real World

• GPS navigation — Google Maps, Waze, and every routing engine use a variant of Dijkstra (often A*, which is Dijkstra with a heuristic)
• Network routing — OSPF (Open Shortest Path First) protocol runs Dijkstra to find the best path through a network
• Social networks — Finding degrees of separation between people
• Game AI — Pathfinding for NPCs in grid-based worlds
• Supply chain — Optimizing delivery routes and logistics

Dijkstra vs A*

Dijkstra explores blindly in all directions. A* adds a heuristic — an estimate of remaining distance — to bias the search toward the goal:

// Dijkstra's priority: distance to node
pq.add(new NodeEntry(node, distanceFromSource));

// A* priority: distance to node + estimated distance to target
pq.add(new NodeEntry(node, distanceFromSource + heuristic(node, target)));

If your heuristic is admissible (never overestimates), A* is guaranteed to find the optimal path while exploring far fewer nodes than Dijkstra. On a 2D grid, the straight-line distance makes an excellent heuristic.

The Bottom Line

Dijkstra’s algorithm finds the shortest path from a source to all other nodes in a graph with non-negative weights. It’s greedy, it uses a priority queue, and it runs in O((V + E) log V) time.

The implementation is compact — under 30 lines of real logic. Once you understand the relax operation (the “is there a shorter path through this node?” check), the rest follows naturally:

1. Initialize distances to infinity, source to 0
2. Pop the closest unvisited node from the min-heap
3. Relax its neighbors — update distances if a shorter path is found
4. Repeat until the heap is empty

That’s it. Sixty years later, still the foundation of how computers find their way from A to B.

Pro Tip: If you only care about the shortest path to a single target, you can early-exit the loop when you pop the target node from the priority queue. Once a node is popped, its shortest distance is finalized — no future iteration will improve it.