Dijkstra, 0-1 BFS & Kruskal's MST
Master Dijkstra's algorithm for shortest paths, 0-1 BFS for weighted graphs with 0/1 weights, and Kruskal's MST.
Dijkstra, 0-1 BFS & Kruskal's MST
Shortest paths and minimum spanning trees are among the most important graph algorithms. Dijkstra finds shortest paths in weighted graphs; Kruskal's finds the minimum cost to connect all vertices.
Dijkstra's Algorithm
Finds the shortest path from a source to all vertices in a weighted graph with non-negative edge weights.
Implementation with Priority Queue
vector<long long> dijkstra(vector<vector<pair<int,int>>> &adj, int source) {
int n = adj.size();
vector<long long> dist(n, LLONG_MAX);
// min-heap: {distance, node}
priority_queue<pair<long long,int>, vector<pair<long long,int>>, greater<>> pq;
dist[source] = 0;
pq.push({0, source});
while (!pq.empty()) {
auto [d, u] = pq.top(); pq.pop();
if (d > dist[u]) continue; // stale entry
for (auto [v, w] : adj[u]) {
if (dist[u] + w < dist[v]) {
dist[v] = dist[u] + w;
pq.push({dist[v], v});
}
}
}
return dist;
}
Time Complexity
O((n + m) log n) with a binary heap.
When to Use Dijkstra
- Non-negative edge weights
- Single-source shortest path
- Need distances to all nodes
When NOT to Use Dijkstra
- Negative edge weights → use Bellman-Ford
- Need shortest paths between all pairs → use Floyd-Warshall
Reconstructing the Path
vector<long long> dist(n, LLONG_MAX);
vector<int> parent(n, -1);
// In Dijkstra, when updating dist[v]:
// parent[v] = u;
// Reconstruct path from source to target
vector<int> path;
int cur = target;
while (cur != -1) {
path.push_back(cur);
cur = parent[cur];
}
reverse(path.begin(), path.end());
0-1 BFS
For graphs where edge weights are only 0 or 1, use a deque instead of a priority queue:
vector<int> zeroOneBFS(vector<vector<pair<int,int>>> &adj, int source) {
int n = adj.size();
vector<int> dist(n, INT_MAX);
deque<int> dq;
dist[source] = 0;
dq.push_front(source);
while (!dq.empty()) {
int u = dq.front(); dq.pop_front();
for (auto [v, w] : adj[u]) {
if (dist[u] + w < dist[v]) {
dist[v] = dist[u] + w;
if (w == 0) dq.push_front(v);
else dq.push_back(v);
}
}
}
return dist;
}
Time Complexity
O(n + m) — linear, faster than Dijkstra for 0/1 weights.
When to Use 0-1 BFS
- Edge weights are only 0 or 1
- Converting a problem to shortest path where moving "forward" costs 0 and "backward" costs 1
- Finding minimum number of operations to transform one state to another
Minimum Spanning Tree — Kruskal's Algorithm
A Minimum Spanning Tree (MST) connects all vertices with minimum total edge weight, without cycles.
Kruskal's Algorithm
- Sort edges by weight
- Process edges from smallest to largest
- Add edge if it doesn't create a cycle (use DSU to check)
struct Edge { int u, v, w; };
long long kruskal(int n, vector<Edge> &edges) {
sort(edges.begin(), edges.end(), [](const Edge &a, const Edge &b) {
return a.w < b.w;
});
DSU dsu(n);
long long mstWeight = 0;
int edgesUsed = 0;
for (auto &[u, v, w] : edges) {
if (dsu.find(u) != dsu.find(v)) {
dsu.unite(u, v);
mstWeight += w;
edgesUsed++;
if (edgesUsed == n - 1) break; // MST has n-1 edges
}
}
return mstWeight;
}
Time Complexity
O(m log m) for sorting + O(m α(n)) for DSU operations = O(m log m).
Prim's Algorithm (Alternative)
Starts from a vertex and grows the MST one edge at a time:
long long prim(vector<vector<pair<int,int>>> &adj) {
int n = adj.size();
vector<bool> inMST(n, false);
priority_queue<pair<int,int>, vector<pair<int,int>>, greater<>> pq;
pq.push({0, 0});
long long totalWeight = 0;
while (!pq.empty()) {
auto [w, u] = pq.top(); pq.pop();
if (inMST[u]) continue;
inMST[u] = true;
totalWeight += w;
for (auto [v, weight] : adj[u]) {
if (!inMST[v]) pq.push({weight, v});
}
}
return totalWeight;
}
Summary
- Dijkstra: O((n+m) log n), shortest paths with non-negative weights
- 0-1 BFS: O(n+m), shortest paths with 0/1 weights only
- Kruskal's: O(m log m), MST using DSU
- Prim's: O((n+m) log n), MST using priority queue (grows from one vertex)
- Always check for negative weights before using Dijkstra
Prefer reading offline? Download the full book as a PDF.
Download Free Book