Log inSign up
mediumGeeksforGeeksNot Started

Dijkstra Shortest Path

Given a weighted, undirected and connected graph of V vertices and an adjacency list adj where adj[i] contains pairs of [neighbor, weight]. Find the shortest distance of all the vertices from the source vertex S.

Graph
Solve on GeeksforGeeks
Lesson

Problem Statement

### Problem Statement

Given an integer V representing the number of vertices in a connected, undirected graph with non-negative edge weights, an adjacency list adj where adj[u] is a list of pairs [v, w] indicating an undirected edge between u and v with weight w, and a source vertex src.

Find the shortest distance from src to all other vertices 0 to V - 1.

Return an array dist of size V where dist[i] denotes the shortest distance from src to vertex i.

---

### Examples

Example 1: ``text Input: V = 3, adj = [[[1, 1], [2, 6]], [[2, 3], [0, 1]], [[1, 3], [0, 6]]], src = 2 Output: [4, 3, 0] Explanation: - Distance from 2 to 2 = 0 - Distance from 2 to 1 = 3 (direct edge 2 -> 1 of weight 3) - Distance from 2 to 0 = 2 -> 1 -> 0 (3 + 1 = 4), which is shorter than direct edge 2 -> 0 of weight 6.

Example 2: ``text Input: V = 2, adj = [[[1, 9]], [[0, 9]]], src = 0 Output: [0, 9]

---

### Constraints - 1 <= V <= 10^5 - 0 <= adj[i].length <= V - 0 <= w <= 10^5 - All weights are non-negative. - Graph is 0-indexed.

Constraints:

  • 1 <= V <= 105
  • 0 <= E <= 105
  • 0 <= w <= 105 (non-negative)
  • 0 <= src < V

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Prove why non-negative edge weights are required for Dijkstra's greedy correctness.
  • Implement Dijkstra using Min-Heap / Priority Queue in multiple languages.
  • Understand the lazy evaluation pattern if (d > dist[u]) continue;.
  • Analyze time and space complexity differences between dense matrix and sparse adjacency list representations.

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • Shortest path or minimum latency in weighted networks with non-negative weights.
  • Cheapest flights/routes with fuel or toll constraints.
  • Minimizing maximum edge weights on a path (minimax path).

Algorithmic Decision Tree:

  • If uniform weights (all w = 1) -> Simple BFS in O(V + E) without heap overhead.
  • If non-negative weights (w >= 0) -> Dijkstra in O((V + E) log V).
  • If any negative weights (w < 0) -> Bellman-Ford in O(V * E).

Connected Patterns:

Breadth First SearchBellman Ford AlgorithmPrim's Minimum Spanning Tree

1. Linear Scan (Matrix / Array-based Dijkstra)

Intuition

In each of V rounds, scan all vertices to find the unvisited node with minimum distance, then relax all its outgoing edges.

Algorithm

  1. Create dist array of size V initialized to INF, set dist[src] = 0.
  2. Create visited boolean array initialized to false.
  3. Repeat V times:
  4. Find unvisited vertex u with minimum dist[u].
  5. Mark visited[u] = true.
  6. For every neighbor v of u: relax dist[v] = min(dist[v], dist[u] + weight).
  7. Return dist array.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <algorithm>
4
5using namespace std;
6
7const int INF = 1e9;
8
9vector<int> dijkstraLinear(int V, const vector<vector<pair<int, int>>>& adj, int src) {
10 vector<int> dist(V, INF);
11 vector<bool> visited(V, false);
12 dist[src] = 0;
13
14 for (int i = 0; i < V; ++i) {
15 int u = -1;
16 for (int j = 0; j < V; ++j) {
17 if (!visited[j] && (u == -1 || dist[j] < dist[u])) {
18 u = j;
19 }
20 }
21
22 if (dist[u] == INF) break;
23 visited[u] = true;
24
25 for (const auto& edge : adj[u]) {
26 int v = edge.first, w = edge.second;
27 if (dist[u] + w < dist[v]) {
28 dist[v] = dist[u] + w;
29 }
30 }
31 }
32 return dist;
33}
34
35int main() {
36 int V = 3;
37 vector<vector<pair<int, int>>> adj(V);
38 adj[2].push_back({1, 3}); adj[1].push_back({2, 3});
39 adj[2].push_back({0, 6}); adj[0].push_back({2, 6});
40 adj[1].push_back({0, 1}); adj[0].push_back({1, 1});
41
42 auto res = dijkstraLinear(V, adj, 2);
43 cout << "Linear Scan Dijkstra: ";
44 for (int d : res) cout << d << " ";
45 cout << endl;
46 return 0;
47}

Time & Space Complexity

  • Time complexity: O(V^2)
  • Space complexity: O(V)

2. FIFO Queue-Based Relaxation (SPFA Algorithm)

Intuition

Push updated nodes into a FIFO queue. Avoids scanning all vertices, but can re-enqueue nodes multiple times.

Algorithm

  1. Initialize dist array with INF, set dist[src] = 0.
  2. Push src into a FIFO queue and mark inQueue[src] = true.
  3. While queue is not empty:
  4. Pop vertex u, set inQueue[u] = false.
  5. For each neighbor (v, w) of u:
  6. If dist[u] + w < dist[v]:
  7. Set dist[v] = dist[u] + w.
  8. If !inQueue[v]: push v into queue, set inQueue[v] = true.
  9. Return dist array.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <queue>
4
5using namespace std;
6
7const int INF = 1e9;
8
9vector<int> spfa(int V, const vector<vector<pair<int, int>>>& adj, int src) {
10 vector<int> dist(V, INF);
11 vector<bool> inQueue(V, false);
12 queue<int> q;
13
14 dist[src] = 0;
15 q.push(src);
16 inQueue[src] = true;
17
18 while (!q.empty()) {
19 int u = q.front();
20 q.pop();
21 inQueue[u] = false;
22
23 for (const auto& edge : adj[u]) {
24 int v = edge.first, w = edge.second;
25 if (dist[u] + w < dist[v]) {
26 dist[v] = dist[u] + w;
27 if (!inQueue[v]) {
28 q.push(v);
29 inQueue[v] = true;
30 }
31 }
32 }
33 }
34 return dist;
35}
36
37int main() {
38 int V = 3;
39 vector<vector<pair<int, int>>> adj(V);
40 adj[2].push_back({1, 3}); adj[1].push_back({2, 3});
41 adj[2].push_back({0, 6}); adj[0].push_back({2, 6});
42 adj[1].push_back({0, 1}); adj[0].push_back({1, 1});
43
44 auto res = spfa(V, adj, 2);
45 cout << "SPFA Result: ";
46 for (int d : res) cout << d << " ";
47 cout << endl;
48 return 0;
49}

Time & Space Complexity

  • Time complexity: O(V * E) worst case, O(E) average
  • Space complexity: O(V)

3. Dijkstra via Min-Heap Priority Queue

Intuition

Standard optimal implementation using a binary min-heap to pick the minimum distance node in O(log V) time.

Algorithm

  1. Initialize dist array of size V with INF (1e9), set dist[src] = 0.
  2. Initialize min-heap priority queue and push (0, src).
  3. While priority queue is not empty:
  4. Extract top element (d, u).
  5. If d > dist[u], continue (stale/outdated entry check).
  6. For each neighbor [v, w] of u:
  7. If dist[u] + w < dist[v]:
  8. Set dist[v] = dist[u] + w.
  9. Push (dist[v], v) into the priority queue.
  10. Return dist array.

Min-Heap Dijkstra Step-by-Step

2 of 2 questions left today
Step 1 / 5
Trace timeline20% explored
Current operationSTEP 1 OF 5
Init dist = [INF, INF, 0]
Visual state
Values and pointers at this exact step
table
This Binary Heap trace has no visual items for the current step yet. Add step.items (and connections where needed) to render its structure accurately.
Decision / next transition
Pop (0, 2)
Why this step matters

Init dist = [INF, INF, 0]. Push (0, 2) to heap.

Step 1 / 5
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <queue>
4
5using namespace std;
6
7const int INF = 1e9;
8
9vector<int> dijkstra(int V, const vector<vector<pair<int, int>>>& adj, int src) {
10 vector<int> dist(V, INF);
11 priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
12
13 dist[src] = 0;
14 pq.push({0, src});
15
16 while (!pq.empty()) {
17 auto [d, u] = pq.top();
18 pq.pop();
19
20 if (d > dist[u]) continue; // Discard outdated entries
21
22 for (const auto& edge : adj[u]) {
23 int v = edge.first, w = edge.second;
24 if (dist[u] + w < dist[v]) {
25 dist[v] = dist[u] + w;
26 pq.push({dist[v], v});
27 }
28 }
29 }
30
31 return dist;
32}
33
34int main() {
35 int V = 3;
36 vector<vector<pair<int, int>>> adj(V);
37 adj[2].push_back({1, 3}); adj[1].push_back({2, 3});
38 adj[2].push_back({0, 6}); adj[0].push_back({2, 6});
39 adj[1].push_back({0, 1}); adj[0].push_back({1, 1});
40
41 int src = 2;
42 vector<int> dist = dijkstra(V, adj, src);
43
44 cout << "Optimal Dijkstra Distances: ";
45 for (int d : dist) cout << d << " ";
46 cout << endl;
47 return 0;
48}

Time & Space Complexity

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

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Unoptimized Linear Scan (Array-based)O(V^2)O(V)Maintain dist array. In each iteration, scan all V vertices to pick the unvisited node with minimum distance.Scanning O(V) unvisited nodes V times.
2.Queue Relaxation (SPFA / Bellman-Ford style)O(V * E)O(V)FIFO queue pushes relaxed neighbors. Can push the same vertex repeatedly.Redundant queue insertions.
3.Min-Heap Priority Queue (Optimal for Sparse Graphs)OptimalO((V + E) log V)O(V + E)Min-heap extracts the closest unvisited vertex in O(log V). Neighbors are relaxed and added in O(log V).Priority queue push and pop operations.

Common Pitfalls & Crucial Edge Cases

Omitting the stale entry check (`if (d > dist[u]) continue;`)

Causes TLE on dense graphs with multiple updates per vertex.

Attempting to use Dijkstra on negative weights

Must use Bellman-Ford instead.

Using a max-heap instead of a min-heap

PriorityQueue in Java/C++ must be configured for ascending (min) order.

Crucial Edge Cases to Validate:

  • Disconnected vertices — Distance remains INF (1e9); never extracted from queue.
  • Zero-weight edges — Handled seamlessly without infinite loops because distances do not decrease indefinitely.
  • Single vertex graph (V = 1, E = 0) — Returns [0].
  • Multiple edges between same pair of nodes — Priority queue naturally selects the edge with smaller weight.

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. Clearly state time complexity: O((V + E) log V) with binary heap, or O(E + V log V) with Fibonacci heap.
  2. Discuss how to reconstruct the shortest path: maintain a parent array updated during dist[u] + w < dist[v].
  3. Compare with A* Search: A* is Dijkstra with an admissible heuristic function h(n).

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.Why does Dijkstra's algorithm fail to guarantee correctness when negative edge weights are present?

2.In priority-queue Dijkstra, why is the condition if (d > dist[u]) continue; necessary?

Back to DSA Sheet