Dijkstra finds the shortest path from a source to all other nodes in a weighted graph with non-negative edge weights. It's BFS adapted for weighted graphs — BFS uses a queue, Dijkstra uses a priority queue.
The Algorithm
Start with distance 0 at the source. Repeatedly pick the unvisited node with the smallest known distance, mark it visited, and relax its neighbours (update their distances if a shorter path is found).
C++ — O(V²) naive Dijkstra (no priority queue)
vector dijkstra_naive(vector>>& adj, int start) {
int V = adj.size();
vector dist(V, INT_MAX);
vector visited(V, false);
dist[start] = 0;
for (int t = 0; t < V; t++) {
// Find unvisited node with smallest distance — O(V) scan
int u = -1;
for (int i = 0; i < V; i++)
if (!visited[i] && (u == -1 || dist[i] < dist[u])) u = i;
if (dist[u] == INT_MAX) break;
visited[u] = true;
for (auto& [v, w] : adj[u])
if (dist[u] + w < dist[v])
dist[v] = dist[u] + w;
}
return dist;
}
// O(V²) — fine for dense graphs (V ≤ 2000)
// Bad for sparse graphs — next chapter fixes this
🚨 O(V²) is slow for sparse graphs
The O(V) scan for the minimum runs V times → O(V²). For V=10⁵, that's 10¹⁰ operations. The priority queue version (next chapter) runs in O((V+E) log V).
Key Takeaways
→Dijkstra: finds shortest paths from single source, non-negative weights only.
→Relaxation: dist[v] = min(dist[v], dist[u] + w).
→Naive O(V²). Use a priority queue for sparse graphs.