← Back to DSA Course | Chapter 13: Graphs | Lesson 7 of 10

Shortest Path Dijkstra

Dijkstra's algorithm is like a GPS finding the shortest route from your house to every other place, always visiting the closest unvisited place next.

In this page:

  1. What is Dijkstra
  2. Relaxation
  3. Non-Negative Weights
  4. Example
  5. Complexity
Syntax
markup 
import heapq
dist = {v: float('inf') for v in graph}
dist[source] = 0
heap = [(0, source)]
while heap:
    d, u = heapq.heappop(heap)
    for v, w in graph[u]:
        if d + w < dist[v]:
            dist[v] = d + w
            heapq.heappush(heap, (dist[v], v))

What is Dijkstra

Dijkstra's algorithm finds the shortest distance from one starting vertex to every other vertex, but only works correctly when all edge weights are zero or positive — a negative edge can make it settle on the wrong answer permanently.

Example: What is Dijkstra

#include <iostream>
using namespace std;
int main() {
	int weights[] = {4, 2, -1};
	cout << "Weight -1 present: Dijkstra would settle on a wrong shortest distance here";
	return 0;
}
public class Main {
	public static void main(String[] args) {
		int[] weights = {4, 2, -1};
		System.out.println("Weight -1 present: Dijkstra would settle on a wrong shortest distance here");
	}
}
weights = [4, 2, -1]
print("Weight -1 present: Dijkstra would settle on a wrong shortest distance here")
#include <stdio.h>
int main() {
	int weights[] = {4, 2, -1};
	printf("Weight -1 present: Dijkstra would settle on a wrong shortest distance here");
	return 0;
}

Relaxation

Relaxing an edge means checking whether going through it gives a shorter known distance to a vertex than what's currently recorded, and updating that distance if so — the core operation repeated throughout the algorithm.

Example: Relaxation

#include <iostream>
using namespace std;
int main() {
	int dist[] = {0, 10, 1000000};
	int u = 1, v = 2, weight = 3;
	if (dist[u] + weight < dist[v]) {
		cout << "Relax: dist[" << v << "] updated from " << dist[v] << " to " << dist[u]+weight;
		dist[v] = dist[u] + weight;
	}
	return 0;
}
public class Main {
	public static void main(String[] args) {
		int[] dist = {0, 10, 1000000};
		int u = 1, v = 2, weight = 3;
		if (dist[u] + weight < dist[v]) {
			System.out.println("Relax: dist[" + v + "] updated from " + dist[v] + " to " + (dist[u]+weight));
		}
	}
}
dist = [0, 10, 1000000]
u, v, weight = 1, 2, 3
if dist[u] + weight < dist[v]:
    print(f"Relax: dist[{v}] updated from {dist[v]} to {dist[u]+weight}")
#include <stdio.h>
int main() {
	int dist[] = {0, 10, 1000000};
	int u = 1, v = 2, weight = 3;
	if (dist[u] + weight < dist[v]) printf("Relax: dist[%d] updated from %d to %d", v, dist[v], dist[u]+weight);
	return 0;
}

Non-Negative Weights

The non-negative-weight requirement exists because Dijkstra permanently finalizes a vertex's distance once it's processed, assuming no future discovery could ever produce a shorter path — a guarantee that breaks the instant a negative edge is allowed.

Example: Non-Negative Weights

#include <iostream>
using namespace std;
int main() {
	int finalized = 5;
	cout << "Vertex " << finalized << " finalized: no future edge can ever shorten it since all weights are >= 0";
	return 0;
}
public class Main {
	public static void main(String[] args) {
		int finalized = 5;
		System.out.println("Vertex " + finalized + " finalized: no future edge can ever shorten it since all weights are >= 0");
	}
}
finalized = 5
print(f"Vertex {finalized} finalized: no future edge can ever shorten it since all weights are >= 0")
#include <stdio.h>
int main() {
	int finalized = 5;
	printf("Vertex %d finalized: no future edge can ever shorten it since all weights are >= 0", finalized);
	return 0;
}

Example

Picture a road network where every road has a positive travel time: starting from one city, Dijkstra discovers the shortest travel time to every other city by always expanding outward from the currently-closest unvisited city.

Example: Example

#include <iostream>
#include <vector>
#include <queue>
using namespace std;
int main() {
	vector<vector<pair<int,int>>> adj = {{{1,4},{2,1}},{{3,1}},{{1,1},{3,5}},{}};
	vector<int> dist(4, 1000000); dist[0] = 0;
	priority_queue<pair<int,int>, vector<pair<int,int>>, greater<>> pq;
	pq.push({0,0});
	while (!pq.empty()) {
		auto [d,u] = pq.top(); pq.pop();
		if (d > dist[u]) continue;
		for (auto [v,w] : adj[u]) if (dist[u]+w < dist[v]) { dist[v]=dist[u]+w; pq.push({dist[v],v}); }
	}
	cout << "Shortest travel time to city 3: " << dist[3];
	return 0;
}
import java.util.*;
public class Main {
	public static void main(String[] args) {
		int[][][] adj = {{{1,4},{2,1}},{{3,1}},{{1,1},{3,5}},{}};
		int[] dist = {0,1000000,1000000,1000000};
		PriorityQueue<int[]> pq = new PriorityQueue<>((a,b)->a[0]-b[0]);
		pq.add(new int[]{0,0});
		while (!pq.isEmpty()) {
			int[] cur = pq.poll();
			int d = cur[0], u = cur[1];
			if (d > dist[u]) continue;
			for (int[] edge : adj[u]) {
				int v = edge[0], w = edge[1];
				if (dist[u]+w < dist[v]) { dist[v] = dist[u]+w; pq.add(new int[]{dist[v],v}); }
			}
		}
		System.out.println("Shortest travel time to city 3: " + dist[3]);
	}
}
import heapq
adj = [[(1,4),(2,1)],[(3,1)],[(1,1),(3,5)],[]]
dist = [1000000]*4
dist[0] = 0
pq = [(0,0)]
while pq:
    d, u = heapq.heappop(pq)
    if d > dist[u]:
        continue
    for v, w in adj[u]:
        if dist[u] + w < dist[v]:
            dist[v] = dist[u] + w
            heapq.heappush(pq, (dist[v], v))
print("Shortest travel time to city 3:", dist[3])
#include <stdio.h>
int main() {
	int dist[4] = {0, 1000000, 1000000, 1000000};
	int edges[4][3] = {{0,1,4},{0,2,1},{2,1,1},{2,3,5}};
	for (int pass = 0; pass < 3; pass++)
		for (int i = 0; i < 4; i++)
			if (dist[edges[i][0]] + edges[i][2] < dist[edges[i][1]])
				dist[edges[i][1]] = dist[edges[i][0]] + edges[i][2];
	printf("Shortest travel time to city 3: %d", dist[3]);
	return 0;
}

Complexity

Using a min-priority queue to always pick the next-closest vertex brings the running time down to roughly O((V+E) log V); a naive array scan without a heap costs O(V²), which is fine for small or dense graphs but slow for large sparse ones.

Example: Complexity

#include <iostream>
using namespace std;
int main() {
	cout << "Dijkstra with min-heap: O((V+E) log V); naive array scan: O(V^2)";
	return 0;
}
public class Main {
	public static void main(String[] args) {
		System.out.println("Dijkstra with min-heap: O((V+E) log V); naive array scan: O(V^2)");
	}
}
print("Dijkstra with min-heap: O((V+E) log V); naive array scan: O(V^2)")
#include <stdio.h>
int main() {
	printf("Dijkstra with min-heap: O((V+E) log V); naive array scan: O(V^2)");
	return 0;
}
Related Topics

Shortest Path Bellman-Ford · Topological Sort · Cycle Detection · Minimum Spanning Tree Kruskal

{# common_mistakes/chapter_summary/browser_support: on Hindi pages the view already swaps in the hi_ translation fields (or blanks these out if untranslated), so this renders correctly for both languages without a lang_code check here. #}
Common Mistakes
  1. Running Dijkstra on a graph with negative weights, which can give wrong distances.
  2. Initializing distances to INT_MAX and then adding a weight to it, which overflows.
  3. Processing a vertex again after its distance is finalized, or forgetting to skip stale queue entries.
🔒

Chapter Quiz — Complete all 10 topics to unlock

0/10 topics done

Complete these topics first:

← Previous Lesson Topological Sort Next Lesson → Shortest Path Bellman-Ford

Login to run this code

C/C++/Java/PHP execution requires a free account. Your code is saved — you'll land right back in the editor after logging in.