Dijkstra’s Algorithm finds the shortest path from a source node in a graph where all edge weights are non-negative.

Its biggest advantage is:

It efficiently finds minimum distances in weighted graphs using a Priority Queue.

Focus on recognizing:

“Weighted graph” + “Shortest path” + “No negative weights” = Dijkstra

Pattern Table

Pattern	Typical Questions	Trigger
Single Source	Distance to all nodes	Weighted shortest path
Source → Destination	Minimum cost A → B	One target
Path Reconstruction	Return actual route	Parent tracking
Grid Dijkstra	Minimum-cost grid path	Weighted cells/edges
Counting Paths	Number of shortest routes	Distance + ways
State Dijkstra	Extra constraints	`(node, state)`

Mental Trigger

Priority Queue + Minimum Distance + Non-Negative Weights → Dijkstra

When NOT to Use Dijkstra

Negative edge weights

Use Bellman-Ford.

Negative cycle detection

Use Bellman-Ford.

Unweighted shortest path

Use BFS.

1. Generic Dijkstra Template (Base)

This is the only Dijkstra template you should memorize.

See the greedy settle-and-relax loop in action — including the moment a shorter two-hop path beats a direct edge:

Dijkstra's Algorithm

Shortest paths from a source on a graph with non-negative weights.

Repeatedly settle the unsettled node with the smallest distance, then relax its outgoing edges (dist[v] = min(dist[v], dist[u]+w)). A settled distance can never improve. Greedy + relaxation is correct only with non-negative weights.

GRAPH VISUALIZER

Steps –

Press ▶ to animate, or step through manually.

Variables

keys: ← → space F

Pseudocode


                        1
                        dist[] = {S:0, rest:∞}
                      
                        2
                        while unsettled nodes remain:
                      
                        3
                          u = unsettled node with SMALLEST dist
                      
                        4
                          settle(u)
                      
                        5
                          for each edge (u → v):
                      
                        6
                            dist[v] = min(dist[v], dist[u] + w)

public int[] dijkstra(List<List<int[]>> graph, int source) {

    int n = graph.size();

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

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

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

    while (!pq.isEmpty()) {

        int[] current = pq.poll();

        int node = current[0];
        int distance = current[1];

        // Ignore stale priority queue entries
        if (distance > dist[node]) {
            continue;
        }

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

            int neighbor = edge[0];
            int weight = edge[1];

            int newDistance = distance + weight;

            if (newDistance < dist[neighbor]) {

                dist[neighbor] = newDistance;

                pq.offer(new int[]{
                        neighbor,
                        newDistance
                });
            }
        }
    }

    return dist;
}

import heapq

def dijkstra(graph, source):
    n = len(graph)

    dist = [float('inf')] * n

    # (distance, node)
    pq = [(0, source)]

    dist[source] = 0

    while pq:

        distance, node = heapq.heappop(pq)

        # Ignore stale priority queue entries
        if distance > dist[node]:
            continue

        for neighbor, weight in graph[node]:

            new_distance = distance + weight

            if new_distance < dist[neighbor]:

                dist[neighbor] = new_distance

                heapq.heappush(
                    pq,
                    (new_distance, neighbor)
                )

    return dist

vector<long long> dijkstra(
        vector<vector<pair<int,int>>>& graph,
        int source) {

    int n = graph.size();

    vector<long long> dist(n, LLONG_MAX);

    priority_queue<
        pair<long long,int>,
        vector<pair<long long,int>>,
        greater<>
    > pq;

    dist[source] = 0;
    pq.push({0, source});

    while (!pq.empty()) {

        auto [distance, node] = pq.top();
        pq.pop();

        // Ignore stale priority queue entries
        if (distance > dist[node]) {
            continue;
        }

        for (auto& [neighbor, weight] : graph[node]) {

            long long newDistance = distance + weight;

            if (newDistance < dist[neighbor]) {
                dist[neighbor] = newDistance;
                pq.push({newDistance, neighbor});
            }
        }
    }

    return dist;
}

class MinHeap {
  constructor() {
    this.data = [];
  }

  push(item) {
    this.data.push(item);
    let i = this.data.length - 1;

    while (i > 0) {
      const parent = (i - 1) >> 1;
      if (this.data[parent][1] <= this.data[i][1]) break;
      [this.data[parent], this.data[i]] =
        [this.data[i], this.data[parent]];
      i = parent;
    }
  }

  pop() {
    const top = this.data[0];
    const last = this.data.pop();

    if (this.data.length) {
      this.data[0] = last;

      let i = 0;
      for (;;) {
        const l = 2 * i + 1;
        const r = l + 1;
        let smallest = i;

        if (
          l < this.data.length &&
          this.data[l][1] < this.data[smallest][1]
        ) smallest = l;
        if (
          r < this.data.length &&
          this.data[r][1] < this.data[smallest][1]
        ) smallest = r;

        if (smallest === i) break;

        [this.data[smallest], this.data[i]] =
          [this.data[i], this.data[smallest]];
        i = smallest;
      }
    }

    return top;
  }

  get size() {
    return this.data.length;
  }
}

function dijkstra(graph, source) {
  const n = graph.length;

  const dist = Array(n).fill(Infinity);
  const pq = new MinHeap(); // items: [node, distance]

  dist[source] = 0;
  pq.push([source, 0]);

  while (pq.size) {
    const [node, distance] = pq.pop();

    // Ignore stale priority queue entries
    if (distance > dist[node]) {
      continue;
    }

    for (const [neighbor, weight] of graph[node]) {
      const newDistance = distance + weight;

      if (newDistance < dist[neighbor]) {
        dist[neighbor] = newDistance;
        pq.push([neighbor, newDistance]);
      }
    }
  }

  return dist;
}

Everything else in Dijkstra is a modification of this template.

Graph Representation

Use a weighted adjacency list:

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

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

# graph[u] holds (neighbor, weight) pairs
graph[u].append((v, weight))

vector<vector<pair<int,int>>> graph;

// {neighbor, weight}
graph[u].push_back({v, weight});

// graph[u] holds [neighbor, weight] pairs
graph[u].push([v, weight]);

For example:

0 → 1 (4)
0 → 2 (2)
2 → 1 (1)

What Changed from Basic BFS?

The core BFS structure is:

Queue<Integer> queue;

Dijkstra changes this to:

PriorityQueue<int[]> pq;

because we must process the node with the smallest known distance, not simply the node that entered first.

BFS

First in → First out

Dijkstra

Smallest distance → Process first

Dijkstra = BFS-style graph expansion + Priority Queue + distance relaxation.

Pattern 1: Single Source Shortest Path

Problem Type

Find shortest distance from one source.
Need distances to all nodes.
Graph is weighted.
All weights are non-negative.

Code

public int[] shortestPath(
        List<List<int[]>> graph,
        int source) {

    return dijkstra(graph, source);
}

def shortest_path(graph, source):
    return dijkstra(graph, source)

vector<long long> shortestPath(
        vector<vector<pair<int,int>>>& graph,
        int source) {
    return dijkstra(graph, source);
}

function shortestPath(graph, source) {
  return dijkstra(graph, source);
}

What Changed from the Base Template?

Nothing.

The generic Dijkstra template already solves this problem.

Single Source Shortest Path = Base Dijkstra.

Typical Problems

Network Delay Time
Shortest Path in Weighted Graph

Pattern 2: Source → Destination

Problem Type

Find the minimum cost from one node to another.

Code

public int shortestDistance(
        List<List<int[]>> graph,
        int source,
        int destination) {

    int n = graph.size();

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

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

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

    while (!pq.isEmpty()) {

        int[] current = pq.poll();

        int node = current[0];
        int distance = current[1];

        // Ignore stale entry
        if (distance > dist[node]) {
            continue;
        }

        // First non-stale destination popped
        // has the shortest distance.
        if (node == destination) {
            return distance;
        }

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

            int neighbor = edge[0];
            int weight = edge[1];

            int newDistance = distance + weight;

            if (newDistance < dist[neighbor]) {

                dist[neighbor] = newDistance;

                pq.offer(new int[]{
                        neighbor,
                        newDistance
                });
            }
        }
    }

    return -1;
}

import heapq

def shortest_distance(graph, source, destination):
    n = len(graph)

    dist = [float('inf')] * n

    # (distance, node)
    pq = [(0, source)]

    dist[source] = 0

    while pq:

        distance, node = heapq.heappop(pq)

        # Ignore stale entry
        if distance > dist[node]:
            continue

        # First non-stale destination popped
        # has the shortest distance.
        if node == destination:
            return distance

        for neighbor, weight in graph[node]:

            new_distance = distance + weight

            if new_distance < dist[neighbor]:

                dist[neighbor] = new_distance

                heapq.heappush(
                    pq,
                    (new_distance, neighbor)
                )

    return -1

long long shortestDistance(
        vector<vector<pair<int,int>>>& graph,
        int source,
        int destination) {
    int n = graph.size();

    vector<long long> dist(n, LLONG_MAX);

    priority_queue<
        pair<long long,int>,
        vector<pair<long long,int>>,
        greater<>
    > pq;

    dist[source] = 0;
    pq.push({0, source});

    while (!pq.empty()) {

        auto [distance, node] = pq.top();
        pq.pop();

        // Ignore stale entry
        if (distance > dist[node]) {
            continue;
        }

        // First non-stale destination popped
        // has the shortest distance.
        if (node == destination) {
            return distance;
        }

        for (auto& [neighbor, weight] : graph[node]) {

            long long newDistance = distance + weight;

            if (newDistance < dist[neighbor]) {
                dist[neighbor] = newDistance;
                pq.push({newDistance, neighbor});
            }
        }
    }

    return -1;
}

function shortestDistance(graph, source, destination) {
  const n = graph.length;

  const dist = Array(n).fill(Infinity);
  const pq = new MinHeap(); // items: [node, distance]

  dist[source] = 0;
  pq.push([source, 0]);

  while (pq.size) {
    const [node, distance] = pq.pop();

    // Ignore stale entry
    if (distance > dist[node]) {
      continue;
    }

    // First non-stale destination popped
    // has the shortest distance.
    if (node === destination) {
      return distance;
    }

    for (const [neighbor, weight] of graph[node]) {
      const newDistance = distance + weight;

      if (newDistance < dist[neighbor]) {
        dist[neighbor] = newDistance;
        pq.push([neighbor, newDistance]);
      }
    }
  }

  return -1;
}

What Changed from the Base Template?

Added:

if (node == destination) {
    return distance;
}

because we only care about one destination.

The important detail is:

if (distance > dist[node]) {
    continue;
}

must happen before the destination check.

Source → Destination = Base Dijkstra + Early return for the destination.

Pattern 3: Reconstruct the Shortest Path

Problem Type

Instead of returning:

minimum distance

we need:

actual route

For example:

0 → 2 → 4 → 5

Code

public List<Integer> shortestPathWithRoute(
        List<List<int[]>> graph,
        int source,
        int destination) {

    int n = graph.size();

    int[] dist = new int[n];
    int[] parent = new int[n];

    Arrays.fill(dist, Integer.MAX_VALUE);
    Arrays.fill(parent, -1);

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

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

    while (!pq.isEmpty()) {

        int[] current = pq.poll();

        int node = current[0];
        int distance = current[1];

        if (distance > dist[node]) {
            continue;
        }

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

            int neighbor = edge[0];
            int weight = edge[1];

            int newDistance = distance + weight;

            if (newDistance < dist[neighbor]) {

                dist[neighbor] = newDistance;
                parent[neighbor] = node;

                pq.offer(new int[]{
                        neighbor,
                        newDistance
                });
            }
        }
    }

    if (dist[destination] == Integer.MAX_VALUE) {
        return new ArrayList<>();
    }

    List<Integer> path = new ArrayList<>();

    int current = destination;

    while (current != -1) {
        path.add(current);
        current = parent[current];
    }

    Collections.reverse(path);

    return path;
}

import heapq

def shortest_path_with_route(graph, source, destination):
    n = len(graph)

    dist = [float('inf')] * n
    parent = [-1] * n

    # (distance, node)
    pq = [(0, source)]

    dist[source] = 0

    while pq:

        distance, node = heapq.heappop(pq)

        if distance > dist[node]:
            continue

        for neighbor, weight in graph[node]:

            new_distance = distance + weight

            if new_distance < dist[neighbor]:

                dist[neighbor] = new_distance
                parent[neighbor] = node

                heapq.heappush(
                    pq,
                    (new_distance, neighbor)
                )

    if dist[destination] == float('inf'):
        return []

    path = []
    current = destination

    while current != -1:
        path.append(current)
        current = parent[current]

    path.reverse()

    return path

vector<int> shortestPathWithRoute(
        vector<vector<pair<int,int>>>& graph,
        int source,
        int destination) {
    int n = graph.size();

    vector<long long> dist(n, LLONG_MAX);
    vector<int> parent(n, -1);

    priority_queue<
        pair<long long,int>,
        vector<pair<long long,int>>,
        greater<>
    > pq;

    dist[source] = 0;
    pq.push({0, source});

    while (!pq.empty()) {

        auto [distance, node] = pq.top();
        pq.pop();

        if (distance > dist[node]) {
            continue;
        }

        for (auto& [neighbor, weight] : graph[node]) {

            long long newDistance = distance + weight;

            if (newDistance < dist[neighbor]) {
                dist[neighbor] = newDistance;
                parent[neighbor] = node;
                pq.push({newDistance, neighbor});
            }
        }
    }

    if (dist[destination] == LLONG_MAX) {
        return {};
    }

    vector<int> path;

    for (int cur = destination; cur != -1; cur = parent[cur]) {
        path.push_back(cur);
    }

    reverse(path.begin(), path.end());

    return path;
}

function shortestPathWithRoute(graph, source, destination) {
  const n = graph.length;

  const dist = Array(n).fill(Infinity);
  const parent = Array(n).fill(-1);
  const pq = new MinHeap(); // items: [node, distance]

  dist[source] = 0;
  pq.push([source, 0]);

  while (pq.size) {
    const [node, distance] = pq.pop();

    if (distance > dist[node]) {
      continue;
    }

    for (const [neighbor, weight] of graph[node]) {
      const newDistance = distance + weight;

      if (newDistance < dist[neighbor]) {
        dist[neighbor] = newDistance;
        parent[neighbor] = node;
        pq.push([neighbor, newDistance]);
      }
    }
  }

  if (dist[destination] === Infinity) {
    return [];
  }

  const path = [];

  for (let cur = destination; cur !== -1; cur = parent[cur]) {
    path.push(cur);
  }

  path.reverse();

  return path;
}

What Changed from the Base Template?

Added:

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

because we need to remember:

“Which node gave me my best distance?”

During relaxation:

parent[neighbor] = node;

Then reconstruct backward:

destination
    ↑
parent
    ↑
parent
    ↑
source

Finally:

Collections.reverse(path);

Path Reconstruction = Dijkstra + Parent Array.

Pattern 4: Grid Dijkstra

Problem Type

Use Dijkstra when a grid has different movement costs.

Examples:

Minimum-cost path
Minimum effort
Weighted cells
Rising water levels

A grid is simply an implicit graph.

Code

public int gridDijkstra(int[][] grid) {

    int n = grid.length;
    int m = grid[0].length;

    int[][] dist = new int[n][m];

    for (int[] row : dist) {
        Arrays.fill(row, Integer.MAX_VALUE);
    }

    int[][] directions = {
            {1, 0},
            {-1, 0},
            {0, 1},
            {0, -1}
    };

    // {cost, row, col}
    PriorityQueue<int[]> pq =
            new PriorityQueue<>(
                    (a, b) -> Integer.compare(a[0], b[0])
            );

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

    while (!pq.isEmpty()) {

        int[] current = pq.poll();

        int cost = current[0];
        int r = current[1];
        int c = current[2];

        if (cost > dist[r][c]) {
            continue;
        }

        if (r == n - 1 && c == m - 1) {
            return cost;
        }

        for (int[] d : directions) {

            int nr = r + d[0];
            int nc = c + d[1];

            if (nr < 0 || nc < 0 ||
                nr >= n || nc >= m) {
                continue;
            }

            int newCost = cost + grid[nr][nc];

            if (newCost < dist[nr][nc]) {

                dist[nr][nc] = newCost;

                pq.offer(new int[]{
                        newCost,
                        nr,
                        nc
                });
            }
        }
    }

    return -1;
}

import heapq

def grid_dijkstra(grid):
    n, m = len(grid), len(grid[0])

    dist = [
        [float('inf')] * m for _ in range(n)
    ]

    directions = [(1, 0), (-1, 0), (0, 1), (0, -1)]

    # (cost, row, col)
    pq = [(0, 0, 0)]

    dist[0][0] = 0

    while pq:

        cost, r, c = heapq.heappop(pq)

        if cost > dist[r][c]:
            continue

        if r == n - 1 and c == m - 1:
            return cost

        for dr, dc in directions:

            nr, nc = r + dr, c + dc

            if nr < 0 or nc < 0 or nr >= n or nc >= m:
                continue

            new_cost = cost + grid[nr][nc]

            if new_cost < dist[nr][nc]:

                dist[nr][nc] = new_cost

                heapq.heappush(
                    pq,
                    (new_cost, nr, nc)
                )

    return -1

struct Cell {
    int cost;
    int r;
    int c;

    // min-heap by cost
    bool operator>(const Cell& other) const {
        return cost > other.cost;
    }
};

int gridDijkstra(vector<vector<int>>& grid) {
    int n = grid.size();
    int m = grid[0].size();

    vector<vector<long long>> dist(
        n,
        vector<long long>(m, LLONG_MAX)
    );

    int directions[4][2] = {
        {1, 0},
        {-1, 0},
        {0, 1},
        {0, -1}
    };

    priority_queue<Cell, vector<Cell>, greater<>> pq;

    dist[0][0] = 0;
    pq.push({0, 0, 0});

    while (!pq.empty()) {

        auto [cost, r, c] = pq.top();
        pq.pop();

        if (cost > dist[r][c]) {
            continue;
        }

        if (r == n - 1 && c == m - 1) {
            return cost;
        }

        for (auto& d : directions) {

            int nr = r + d[0];
            int nc = c + d[1];

            if (nr < 0 || nc < 0 ||
                nr >= n || nc >= m) {
                continue;
            }

            long long newCost = cost + grid[nr][nc];

            if (newCost < dist[nr][nc]) {
                dist[nr][nc] = newCost;
                pq.push({(int)newCost, nr, nc});
            }
        }
    }

    return -1;
}

function gridDijkstra(grid) {
  const n = grid.length;
  const m = grid[0].length;

  const dist = Array.from({ length: n }, () =>
    Array(m).fill(Infinity)
  );

  const directions = [
    [1, 0],
    [-1, 0],
    [0, 1],
    [0, -1],
  ];

  // items: [cost, row, col]
  const pq = new MinHeap();

  dist[0][0] = 0;
  pq.push([0, 0, 0]);

  while (pq.size) {
    const [cost, r, c] = pq.pop();

    if (cost > dist[r][c]) {
      continue;
    }

    if (r === n - 1 && c === m - 1) {
      return cost;
    }

    for (const [dr, dc] of directions) {
      const nr = r + dr;
      const nc = c + dc;

      if (nr < 0 || nc < 0 || nr >= n || nc >= m) {
        continue;
      }

      const newCost = cost + grid[nr][nc];

      if (newCost < dist[nr][nc]) {
        dist[nr][nc] = newCost;
        pq.push([newCost, nr, nc]);
      }
    }
  }

  return -1;
}

What Changed from the Base Template?

Node becomes a cell

Base:

int node

Changed:

int r, int c

Neighbors are generated using directions

Base:

for (int[] edge : graph.get(node))

Changed:

for (int[] d : directions)

Distance becomes 2D

Base:

int[] dist

Changed:

int[][] dist

Grid Dijkstra = Base Dijkstra + 2D distance + directions.

Pattern 5: Counting Shortest Paths

Problem Type

Find:

How many different shortest paths reach the destination?

We now track two things:

dist[node] = shortest distance
ways[node] = number of shortest paths

Code

Core transition:

if (newDistance < dist[neighbor]) {

    dist[neighbor] = newDistance;

    ways[neighbor] = ways[node];

    pq.offer(new int[]{
            neighbor,
            newDistance
    });

} else if (newDistance == dist[neighbor]) {

    ways[neighbor] += ways[node];
}

Initialize:

long[] ways = new long[n];

ways[source] = 1;

What Changed from the Base Template?

Added:

ways[]

because distance alone doesn’t tell us how many shortest paths exist.

Two cases matter:

Found a better distance

newDistance < dist[neighbor]

Replace the old answer:

ways[neighbor] = ways[node];

Found another equally short path

newDistance == dist[neighbor]

Add the number of ways:

ways[neighbor] += ways[node];

Counting Paths = Dijkstra + Distance + Number of Ways.

Pattern 6: State Dijkstra

Problem Type

Sometimes the real state is not just:

node

It is:

(node, extra information)

Examples:

(node, stops)
(node, fuel)
(node, discountUsed)
(node, keysCollected)

Example State

Suppose a discount can be used once.

The state becomes:

(node, discountUsed)

So instead of:

int[] dist = new int[n];

we might need:

int[][] dist = new int[n][2];

where:

dist[node][0] = discount unused
dist[node][1] = discount already used

Priority Queue

PriorityQueue<State> pq;

A custom state class is often cleaner:

static class State {
    int node;
    int cost;
    int state;

    State(int node, int cost, int state) {
        this.node = node;
        this.cost = cost;
        this.state = state;
    }
}

from dataclasses import dataclass

@dataclass
class State:
    node: int
    cost: int
    state: int

struct State {
    int node;
    int cost;
    int state;
};

// { node, cost, state } objects are used directly:
pq.push({ node, cost, state });

What Changed from the Base Template?

Base state:

node

Changed state:

node + extra constraint

Therefore the distance array also becomes multidimensional.

State Dijkstra = Dijkstra + Expand the definition of a state.

Important Note: K Stops

Problems such as:

Cheapest Flights Within K Stops

should not automatically be treated as ordinary Dijkstra.

The stop count is part of the state:

(node, stops)

A layered Bellman-Ford approach or state-based shortest-path solution is often more appropriate.

Recognition Trigger

Shortest path + additional constraint = think State Dijkstra / layered shortest path.

Dijkstra Pattern Evolution

Base Dijkstra
    ↓
Single Source
    (same template)

Source → Destination
    (+ early return)

Path Reconstruction
    (+ parent array)

Grid Dijkstra
    (+ directions + 2D distance)

Counting Paths
    (+ ways array)

State Dijkstra
    (+ extra state dimension)

Common Mistakes

1. Using Dijkstra with Negative Weights

Example:

0 → 1 (5)
0 → 2 (2)
2 → 1 (-10)

Dijkstra is not valid when negative edges exist.

Use:

Bellman-Ford

instead.

2. Forgetting the Stale Entry Check

The priority queue can contain multiple entries for the same node.

Example:

node 3 → distance 10
node 3 → distance 5

When 5 becomes the best distance, the old 10 entry can still remain in the queue.

Use:

if (distance > dist[node]) {
    continue;
}

Priority Queue contains candidates, not necessarily the latest distance.

3. Using `visited[]` Instead of Distance Checks

A common template is:

visited[node] = true;

But for most Dijkstra implementations, the stale-entry check is cleaner:

if (distance > dist[node]) {
    continue;
}

This is especially important when the state is modified or multiple queue entries exist.

4. Using BFS for Weighted Graphs

Wrong:

Queue<Integer>

for general weighted shortest paths.

Correct:

PriorityQueue<int[]>

when weights are non-negative.

5. Using Dijkstra for Unweighted Graphs

If every edge has equal cost:

Use BFS.

Dijkstra works conceptually, but BFS is simpler and faster.

6. Integer Overflow

Avoid:

(a, b) -> a[1] - b[1]

because subtraction can overflow.

Prefer:

(a, b) -> Integer.compare(a[1], b[1])

For very large path costs, consider using long for distances.

Complexity

With an adjacency list and binary heap:

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

Often simplified to:

O(E log V)

for connected graphs.

Recognition Cheat Sheet

If you see…	Think…
Weighted shortest path	Dijkstra
Non-negative weights	Dijkstra
Minimum cost route	Dijkstra
One source → all nodes	Dijkstra
One source → one target	Dijkstra + early exit
Need actual route	Dijkstra + parent
Weighted grid	Grid Dijkstra
Count shortest routes	Dijkstra + ways
Extra constraint	State Dijkstra
Negative edge	Bellman-Ford
Unweighted graph	BFS

Dijkstra vs BFS vs Bellman-Ford

Feature	BFS	Dijkstra	Bellman-Ford
Unweighted graph	✅	✅*	✅
Non-negative weighted graph	❌	✅	✅
Negative weights	❌	❌	✅
Negative cycle detection	❌	❌	✅
Data structure	Queue	Priority Queue	Edge relaxation
Complexity	`O(V + E)`	`O((V + E) log V)`	`O(V × E)`

Dijkstra can technically handle equal-weight edges, but BFS is the natural choice.

Earn Premium with Referrals

Pattern Table

Mental Trigger

When NOT to Use Dijkstra

Negative edge weights

Negative cycle detection

Unweighted shortest path

1. Generic Dijkstra Template (Base)

Dijkstra's Algorithm

Graph Representation

What Changed from Basic BFS?

BFS

Dijkstra

Pattern 1: Single Source Shortest Path

Problem Type

Code

What Changed from the Base Template?

Typical Problems

Pattern 2: Source → Destination

Problem Type

Code

What Changed from the Base Template?

Pattern 3: Reconstruct the Shortest Path

Problem Type

Code

What Changed from the Base Template?

Pattern 4: Grid Dijkstra

Problem Type

Code

What Changed from the Base Template?

Node becomes a cell

Neighbors are generated using directions

Distance becomes 2D

Pattern 5: Counting Shortest Paths

Problem Type

Code

What Changed from the Base Template?

Found a better distance

Found another equally short path

Pattern 6: State Dijkstra

Problem Type

Example State

Priority Queue

What Changed from the Base Template?

Important Note: K Stops

Recognition Trigger

Dijkstra Pattern Evolution

Common Mistakes

1. Using Dijkstra with Negative Weights

2. Forgetting the Stale Entry Check

3. Using visited[] Instead of Distance Checks

4. Using BFS for Weighted Graphs

5. Using Dijkstra for Unweighted Graphs

6. Integer Overflow

Complexity

Recognition Cheat Sheet

Dijkstra vs BFS vs Bellman-Ford

Premium Content

My Private Notes

3. Using `visited[]` Instead of Distance Checks