How does Dijkstra's Algorithm work?

It maintains a set of "closest" nodes and repeatedly expands the one with the smallest known distance, relaxing its outgoing edges to update neighbors.

Does it work with negative edge weights?

No, Dijkstra's assumes that once a node is processed, its distance is final. Negative weights can break this greedy assumption.

What is the time complexity of Dijkstra's algorithm?

Using a Binary Heap (Priority Queue), it is O((V+E) log V). With a Fibonacci Heap, it can reach O(E + V log V).

Dijkstra's Algorithm

Dijkstra's algorithm finds the shortest path from a starting node to all other nodes in a weighted graph.

INIT

Priority queue

A:0

Shortest distance

A:0

B:∞

C:∞

D:∞

Every distance starts at ∞ except A, which is 0. Push A.

Pop A at distance 0 — the cheapest unsettled node, so 0 is final.

Source

Intuition

Imagine finding the quickest route on a map. You always take the road that gets you to a new town in the shortest total time.

Once you're sure you've found the fastest way to a town, you use that town to find fast routes to its neighbors.

Concept

Greedy Approach: Always process the closest unvisited node next.
Relaxation: If we find a path to node V through node U that is shorter than the current known path to V, we update (relax) the distance to V.
Priority Queue: Used to efficiently select the node with the smallest tentative distance.

How it Works

Algorithm Steps:

Set distance to start node = 0, all others = ∞.
Add start node to a Priority Queue (PQ).
While PQ is not empty:
- Pop node u with the smallest distance.
- If u is already visited, skip it.
- Mark u as visited.
- For each neighbor v of u with weight w:
  - If dist[u] + w < dist[v]:
  - Update dist[v] = dist[u] + w.
  - Add v to PQ.

Step-by-Step Breakdown

Watch the visualization:

Solid blue node: The node being settled: the smallest tentative distance left in the priority queue.
Pale blue node with a blue outline: The neighbour being relaxed through it.
Blue edge: The connection being checked for a shorter path.
Green node: Settled: its shortest distance is final.
Number above a node: Its current tentative distance from the start.

When to Use

Use Dijkstra's when:

Finding optimal routes in GPS/Navigation systems.
Routing data packets in networks (OSPF, IS-IS).
The graph has non-negative edge weights.

When NOT to Use

Negative Edge Weights: Dijkstra's can fail with negative weights. Use Bellman-Ford instead.
Unweighted Graphs: BFS is simpler and faster (O(V+E) vs O(E log V)).

How to Identify

"Find shortest path", "Minimum cost to reach target", "Weighted positive graph".

AI resume checker — match your resume to the job description

Bipartite Graph

Bellman-Ford Algorithm

Complexity

Time (Best)

O(E log V)

Time (Average)

O(E log V)

Time (Worst)

O(E log V)

Space

O(V + E)

Dijkstra's Algorithm Code

1function dijkstra(n, edges, start) {
2  const adj = Array.from({ length: n }, () => []);
3  for (const [u, v, w] of edges) {
4    adj[u].push([v, w]);
5    adj[v].push([u, w]); // Assuming undirected
6  }
7
8  const dist = new Array(n).fill(Infinity);
9  dist[start] = 0;
10  
11  // Min-Priority Queue implementation needed or use array sort
12  const pq = [[0, start]]; // [distance, node]
13
14  while (pq.length > 0) {
15    pq.sort((a, b) => a[0] - b[0]); // Simple sort for demo
16    const [d, u] = pq.shift();
17
18    if (d > dist[u]) continue;
19
20    for (const [v, w] of adj[u]) {
21      if (dist[u] + w < dist[v]) {
22        dist[v] = dist[u] + w;
23        pq.push([dist[v], v]);
24      }
25    }
26  }
27  return dist;
28}

Related Lessons

Dijkstra's Algorithm

Intuition

Concept

How it Works

Step-by-Step Breakdown

When to Use

When NOT to Use

How to Identify

Sample Problems

Network Delay Time

Cheapest Flights Within K Stops

Path with Maximum Probability

AI resume checker — match your resume to the job description

Stack

Queue

Deque

Circular Queue

Frequently Asked Questions

How does Dijkstra's Algorithm work?

Does it work with negative edge weights?

What is the time complexity of Dijkstra's algorithm?