Shortest Path Dijkstra
In this page:
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;
}Login to try C/C++/Java code in the editor
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;
}Login to try C/C++/Java code in the editor
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;
}Login to try C/C++/Java code in the editor
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;
}Login to try C/C++/Java code in the editor
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;
}Login to try C/C++/Java code in the editor
Chapter Quiz — Complete all 10 topics to unlock
0/10 topics done
Complete these topics first: