Getting everything ready for you…

Loading courses, problems and your progress. This takes just a moment.

0s

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

More DSA notes