Dijkstra's Algorithm Explained Tutorial

Dijkstra's algorithm is a shortest path algorithm used to find the minimum-cost path from a starting vertex to other vertices in a weighted graph. It is especially useful when edge weights are non-negative.

The algorithm is widely used in problems involving maps, computer networks, routing, transportation, and other systems where moving from one point to another has an associated cost.

Dijkstra's algorithm uses a greedy strategy. At each step, it selects the unprocessed vertex with the smallest known distance from the source and uses that vertex to improve the distances of its neighbors.

When Should You Use Dijkstra's Algorithm?

Dijkstra's algorithm is appropriate when the graph has weighted edges and all edge weights are non-negative.

Graph Property	Dijkstra
Weighted graph	Yes
Non-negative edge weights	Required
Negative edge weights	Not suitable
Single source shortest paths	Yes

Example Graph

Consider the following weighted graph:

       4
  A -------- B
  |          |
 2|          |5
  |          |
  C -------- D
       3

If A is the starting vertex, Dijkstra's algorithm calculates the minimum cost required to reach B, C, and D from A.

Core Idea Behind Dijkstra's Algorithm

The algorithm maintains a distance value for every vertex. Initially, the source has distance 0, while every other vertex is assigned Infinity.

A = 0
B = Infinity
C = Infinity
D = Infinity

Whenever a vertex is selected, the algorithm checks whether traveling through that vertex produces a shorter route to each neighbor.

This process is called edge relaxation.

Edge Relaxation

Suppose the current shortest known distance to A is 5 and there is an edge from A to B with weight 3.

distance[A] = 5
weight(A, B) = 3

candidate = distance[A] + weight(A, B)
          = 5 + 3
          = 8

If B currently has a distance greater than 8, its distance is updated to 8. The algorithm can also store A as B's predecessor so the complete route can later be reconstructed.

How Dijkstra's Algorithm Works

Set the source vertex distance to 0.
Set every other vertex distance to infinity.
Select the unvisited vertex with the smallest known distance.
Check all edges leaving the selected vertex.
Relax each neighboring vertex if a shorter route is found.
Mark the selected vertex as processed.
Repeat until the required vertices have been processed.

Step-by-Step Example

Consider this graph:

A -- 4 -- B
|         |
2         3
|         |
C -- 1 -- D

Start at A:

A = 0
B = Infinity
C = Infinity
D = Infinity

Process A. Its neighbors are B and C:

A → B = 4
A → C = 2

Distances:
A = 0
B = 4
C = 2
D = Infinity

C now has the smallest unprocessed distance, so process C next. The route from C to D costs 1:

A → C → D
2 + 1 = 3

Distances:
A = 0
B = 4
C = 2
D = 3

D now has the smallest unprocessed distance. Therefore, the shortest distance from A to D is 3 through C.

Basic JavaScript Implementation

A straightforward implementation can search through all vertices to find the next vertex with the smallest distance.

function dijkstra(graph, start) {
  const distances = {};
  const visited = new Set();

  for (const vertex of Object.keys(graph)) {
    distances[vertex] = Infinity;
  }

  distances[start] = 0;

  while (visited.size < Object.keys(graph).length) {
    let current = null;
    let smallestDistance = Infinity;

    for (const vertex of Object.keys(graph)) {
      if (
        !visited.has(vertex) &&
        distances[vertex] < smallestDistance
      ) {
        smallestDistance = distances[vertex];
        current = vertex;
      }
    }

    if (current === null) {
      break;
    }

    visited.add(current);

    for (const edge of graph[current]) {
      const { node: neighbor, weight } = edge;

      const candidateDistance =
        distances[current] + weight;

      if (candidateDistance < distances[neighbor]) {
        distances[neighbor] = candidateDistance;
      }
    }
  }

  return distances;
}

const graph = {
  A: [
    { node: "B", weight: 4 },
    { node: "C", weight: 2 }
  ],
  B: [
    { node: "D", weight: 3 }
  ],
  C: [
    { node: "D", weight: 1 }
  ],
  D: []
};

console.log(dijkstra(graph, "A"));

The result gives the minimum distance from A to every reachable vertex.

Dijkstra Using a Priority Queue

The simple implementation repeatedly scans every vertex to find the smallest distance. For large graphs, a priority queue implemented with a min-heap is generally more efficient.

The priority queue stores vertices according to their current shortest known distance. The vertex with the smallest distance can then be retrieved efficiently.

Priority Queue

(distance, vertex)

(0, A)
(2, C)
(4, B)
(3, D)

In practical implementations, the priority queue may contain multiple entries for the same vertex. When an outdated entry is removed, it can be ignored if its distance is greater than the current recorded distance.

Priority Queue Implementation

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

  push(item) {
    this.heap.push(item);
    this.bubbleUp(this.heap.length - 1);
  }

  pop() {
    if (this.heap.length === 0) {
      return null;
    }

    const root = this.heap[0];
    const last = this.heap.pop();

    if (this.heap.length > 0) {
      this.heap[0] = last;
      this.bubbleDown(0);
    }

    return root;
  }

  bubbleUp(index) {
    while (index > 0) {
      const parent = Math.floor((index - 1) / 2);

      if (this.heap[parent][0] <= this.heap[index][0]) {
        break;
      }

      [this.heap[parent], this.heap[index]] =
        [this.heap[index], this.heap[parent]];

      index = parent;
    }
  }

  bubbleDown(index) {
    const length = this.heap.length;

    while (true) {
      let smallest = index;
      const left = index * 2 + 1;
      const right = index * 2 + 2;

      if (
        left < length &&
        this.heap[left][0] < this.heap[smallest][0]
      ) {
        smallest = left;
      }

      if (
        right < length &&
        this.heap[right][0] < this.heap[smallest][0]
      ) {
        smallest = right;
      }

      if (smallest === index) {
        break;
      }

      [this.heap[index], this.heap[smallest]] =
        [this.heap[smallest], this.heap[index]];

      index = smallest;
    }
  }

  isEmpty() {
    return this.heap.length === 0;
  }
}

function dijkstra(graph, start) {
  const distances = {};

  for (const vertex of Object.keys(graph)) {
    distances[vertex] = Infinity;
  }

  distances[start] = 0;

  const minHeap = new MinHeap();
  minHeap.push([0, start]);

  while (!minHeap.isEmpty()) {
    const [currentDistance, current] = minHeap.pop();

    if (currentDistance > distances[current]) {
      continue;
    }

    for (const edge of graph[current]) {
      const { node: neighbor, weight } = edge;

      const newDistance =
        currentDistance + weight;

      if (newDistance < distances[neighbor]) {
        distances[neighbor] = newDistance;
        minHeap.push([newDistance, neighbor]);
      }
    }
  }

  return distances;
}

const graph = {
  A: [
    { node: "B", weight: 4 },
    { node: "C", weight: 2 }
  ],
  B: [
    { node: "D", weight: 3 }
  ],
  C: [
    { node: "B", weight: 1 },
    { node: "D", weight: 1 }
  ],
  D: []
};

console.log(dijkstra(graph, "A"));

Reconstructing the Shortest Path

Sometimes knowing the shortest distance is not enough. For example, a navigation system needs to know which locations should be visited.

Store the previous vertex whenever a shorter distance is discovered:

previous[B] = A;
previous[C] = A;
previous[D] = C;

If the destination is D, following the previous references gives:

D ← C ← A

Reverse:

A → C → D

Complete Path Reconstruction Example

function shortestPath(graph, start, target) {
  const distances = {};
  const previous = {};
  const visited = new Set();

  for (const vertex of Object.keys(graph)) {
    distances[vertex] = Infinity;
    previous[vertex] = null;
  }

  distances[start] = 0;

  while (visited.size < Object.keys(graph).length) {
    let current = null;
    let smallestDistance = Infinity;

    for (const vertex of Object.keys(graph)) {
      if (
        !visited.has(vertex) &&
        distances[vertex] < smallestDistance
      ) {
        smallestDistance = distances[vertex];
        current = vertex;
      }
    }

    if (current === null) {
      break;
    }

    visited.add(current);

    for (const edge of graph[current]) {
      const { node: neighbor, weight } = edge;
      const newDistance =
        distances[current] + weight;

      if (newDistance < distances[neighbor]) {
        distances[neighbor] = newDistance;
        previous[neighbor] = current;
      }
    }
  }

  if (distances[target] === Infinity) {
    return null;
  }

  const path = [];
  let current = target;

  while (current !== null) {
    path.push(current);
    current = previous[current];
  }

  path.reverse();

  return {
    distance: distances[target],
    path
  };
}

const graph = {
  A: [
    { node: "B", weight: 4 },
    { node: "C", weight: 2 }
  ],
  B: [
    { node: "D", weight: 5 }
  ],
  C: [
    { node: "B", weight: 1 },
    { node: "D", weight: 1 }
  ],
  D: []
};

console.log(shortestPath(graph, "A", "D"));

Time Complexity

The complexity of Dijkstra's algorithm depends heavily on how the graph and priority queue are implemented.

Implementation	Time Complexity
Simple array / vertex scan	O(V²)
Binary heap + adjacency list	O((V + E) log V)
Space complexity	O(V) auxiliary, excluding graph storage

Here, V represents the number of vertices and E represents the number of edges. With an adjacency list and a binary heap, Dijkstra's algorithm is generally suitable for sparse graphs.

Why Non-Negative Weights Matter

Dijkstra's algorithm depends on a greedy property: after selecting the unprocessed vertex with the smallest distance, its distance can be finalized when all edge weights are non-negative.

A negative edge can invalidate that assumption because a later route may reduce the distance of a vertex that was already considered finalized.

A → B = 4
A → C = 2
C → B = -5

For graphs containing negative edge weights, consider Bellman-Ford instead.

Dijkstra vs BFS

Both algorithms can find shortest paths, but they are designed for different graph conditions.

Feature	BFS	Dijkstra
Typical graph	Unweighted	Weighted
Different edge weights	No	Yes
Negative weights	Not applicable	No
Typical complexity	O(V + E)	O((V + E) log V) with a binary heap

Dijkstra vs Bellman-Ford

Both algorithms solve the single-source shortest path problem, but their handling of edge weights differs.

Dijkstra requires non-negative edge weights.
Bellman-Ford can handle negative edge weights.
Bellman-Ford can detect reachable negative-weight cycles.
Dijkstra is generally faster for graphs that satisfy its non-negative-weight requirement.

Applications of Dijkstra's Algorithm

Navigation Systems

Road networks can be represented as weighted graphs where edge weights represent distance, travel time, or another route cost.

Network Routing

Network nodes can be modeled as vertices and communication costs can be represented by edge weights.

Game Development

Weighted movement between locations can be modeled as a graph to find a minimum-cost route.

Logistics

Transportation networks can use weighted edges to represent distance, time, or transportation cost.

Common Mistakes

Using Dijkstra's algorithm when negative edge weights are present.
Forgetting to initialize every distance to infinity.
Failing to relax edges after selecting a vertex.
Confusing the shortest distance with the actual shortest path.
Forgetting to track predecessors when path reconstruction is required.
Using a simple O(V²) implementation without considering graph size.
Failing to ignore outdated priority queue entries in heap-based implementations.
Assuming that the path with the fewest edges is always the cheapest path.

Dijkstra's Algorithm in Interview Problems

Dijkstra's algorithm commonly appears in coding interviews as a shortest-path pattern. The problem statement may not explicitly mention the algorithm. Instead, look for clues such as:

A graph or network of connected nodes.
A cost, distance, time, or weight associated with each connection.
A requirement to minimize total cost.
Non-negative weights.
A source node from which distances must be calculated.

If the problem asks for a minimum-cost route through a weighted graph and all weights are non-negative, Dijkstra's algorithm should be one of the first approaches to consider.

Key Takeaways

Dijkstra's algorithm finds shortest paths from a source vertex.
It works with weighted graphs containing non-negative edge weights.
The algorithm uses a greedy strategy.
Edge relaxation is the main operation used to improve distances.
A priority queue can make the algorithm more efficient.
Predecessor information can be stored to reconstruct the actual shortest path.
A simple vertex-scan implementation has O(V²) time complexity.
A binary heap with an adjacency list typically provides O((V + E) log V) time complexity.
Dijkstra's algorithm should not be used for graphs with negative edge weights.
For negative edge weights, Bellman-Ford is a suitable alternative.

Topics

Dijkstra's Algorithm Explained