Notes › DSA
Shortest Paths and Minimum Spanning Tree
Builds on Graphs — BFS and DFS.
Which shortest-path algorithm?
| Graph | Algorithm | Time |
|---|---|---|
| Unweighted (all edges equal) | BFS | O(V + E) |
| Weights only 0 or 1 | 0-1 BFS (deque) | O(V + E) |
| Non-negative weights | Dijkstra | O((V + E) log V) |
| Negative weights, no negative cycle | Bellman-Ford | O(V · E) |
| All pairs, small V (≤ ~400) | Floyd-Warshall | O(V³) |
| DAG | topological order + relax | O(V + E) |
Relaxing an edge u → v with weight w: if dist[u] + w < dist[v], update dist[v]. Every algorithm here is a smart order of relaxations.
Dijkstra
Always expand the closest unfinished node, using a min-heap.
vector<long long> dijkstra(int src, vector<vector<pair<int,int>>>& adj) { // adj[u] = {v, w}
vector<long long> dist(adj.size(), LLONG_MAX);
priority_queue<pair<long long,int>, vector<pair<long long,int>>, greater<>> pq;
dist[src] = 0; pq.push({0, src});
while (!pq.empty()) {
auto [d, u] = pq.top(); pq.pop();
if (d > dist[u]) continue; // stale entry, skip
for (auto [v, w] : adj[u])
if (dist[u] + w < dist[v]) {
dist[v] = dist[u] + w;
pq.push({dist[v], v});
}
}
return dist;
}
❗ Dijkstra fails with negative edges — a node can be finalised before a cheaper path through a negative edge is found.
To print the path, store parent[v] = u when relaxing, then walk back from the target.
Bellman-Ford
Relax all edges V − 1 times. If any edge still relaxes on the V-th round, there is a negative cycle.
vector<long long> bellmanFord(int n, vector<array<int,3>>& edges, int src) { // {u, v, w}
vector<long long> dist(n, LLONG_MAX); dist[src] = 0;
for (int i = 0; i < n - 1; i++)
for (auto [u, v, w] : edges)
if (dist[u] != LLONG_MAX && dist[u] + w < dist[v]) dist[v] = dist[u] + w;
for (auto [u, v, w] : edges)
if (dist[u] != LLONG_MAX && dist[u] + w < dist[v]) return {}; // negative cycle
return dist;
}
Also used for "cheapest flights within K stops" (run only K + 1 rounds, copying the array each round).
Floyd-Warshall (all pairs)
// d[i][j] = edge weight, 0 on the diagonal, INF if no edge
for (int k = 0; k < n; k++)
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
if (d[i][k] < INF && d[k][j] < INF) d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
k must be the outer loop. A negative value on the diagonal afterwards means a negative cycle.
0-1 BFS
With weights 0 or 1, use a deque: push to the front for a 0-edge and to the back for a 1-edge.
Minimum Spanning Tree (MST)
A spanning tree connects all V vertices with V − 1 edges; the MST has the smallest total weight. Used for laying cables, roads, network design.
Kruskal's — sort edges by weight, add an edge if it does not form a cycle (union-find). O(E log E).
long long kruskal(int n, vector<array<int,3>>& edges) { // {w, u, v}
sort(edges.begin(), edges.end());
parent.resize(n); sz.assign(n, 1);
iota(parent.begin(), parent.end(), 0);
long long total = 0;
for (auto [w, u, v] : edges) if (unite(u, v)) total += w; // unite from the union-find note
return total;
}
Prim's — grow the tree from a start node, always taking the cheapest edge leaving the tree (min-heap). O(E log V). Better for dense graphs.
Classic problems
| Problem | Algorithm |
|---|---|
| Network delay time | Dijkstra |
| Path with minimum effort / maximum probability | Dijkstra variant |
| Cheapest flights within K stops | Bellman-Ford (K rounds) / BFS |
| Find the city with the smallest number of neighbours | Floyd-Warshall |
| Min cost to connect all points | Prim / Kruskal |
| Shortest path in a grid with obstacles removal | BFS with state |
Practise in the Graphs section.
Interview one-liners
- Dijkstra = BFS with a priority queue; only for non-negative weights.
- Bellman-Ford detects negative cycles; Dijkstra cannot.
- MST is about connecting everything cheaply; shortest path is about one source to others — the MST does not give shortest paths.
- Use
long longfor distances to avoid overflow.