Advanced Graphs — Dijkstra, Bellman-Ford, Floyd-Warshall & MST

Past BFS/DFS: every weighted-graph algorithm you need — Dijkstra, Bellman-Ford, Floyd-Warshall, Kruskal, Prim — each explained with Why → How → When → Code in Python, Java, and C++. Includes a decision table for picking the right algorithm under interview pressure.

graphsshortest-pathdijkstrabellman-fordfloyd-warshallMSTkruskalprim

Why Weighted Graphs Need More Than BFS

BFS/DFS are great for unweighted graphs — where every edge costs the same "1 hop". But in the real world, edges have different costs:

  • 🗺️ Google Maps: Road A takes 5 minutes, Road B takes 30 minutes
  • ✈️ Flight pricing: Some routes cost $200, others cost $800
  • 🌐 Network routing: Some links have 10ms latency, others have 100ms

When edge weights differ, BFS gives you the wrong shortest path. You need algorithms that account for weight.

The Algorithm Decision Table

Before diving in, learn this table. It tells you which algorithm to use in any situation:

ProblemAlgorithmTime ComplexityConstraint
Shortest path, non-negative weightsDijkstraO((V+E) log V)No negative edges
Shortest path, negative edges or negative cycle detectionBellman-FordO(V·E)—
All-pairs shortest pathsFloyd-WarshallO(V³)Small V (≤ ~400)
Shortest path on a DAGTopo sort + relaxationO(V+E)Must be acyclic
Minimum spanning treeKruskal or PrimO(E log E)Undirected, weighted
Bounded hops (at most K edges)Bellman-Ford with K roundsO(K·E)—
How to pick in an interview — 3 key questions
  1. Negative edges? Yes → Bellman-Ford. No → Dijkstra is fine.
  2. Need ALL pairs? Yes → Floyd-Warshall. No → single-source algorithm.
  3. Connect all nodes, minimize cost? → MST (Kruskal or Prim).

Dijkstra — The Workhorse

Why We Need Dijkstra

On a weighted graph, BFS would find the path with the fewest hops, but that might not be the cheapest. Dijkstra greedily always explores the cheapest unvisited node next, guaranteeing that when it reaches any node for the first time, that's the shortest path.

Real-world: Google Maps uses Dijkstra-like algorithms to find the fastest driving route.

How to Approach (Priority Queue + Relaxation)

  1. Initialize: dist[src] = 0, all others = ∞. Push (0, src) into a min-heap.
  2. Process: Pop the cheapest (cost, node) from the heap.
    • If cost > dist[node], skip — this is a stale entry (we already found a better path).
    • For each neighbor v with edge weight w: if dist[node] + w < dist[v], update and push to heap.
  3. Done: After heap is empty, dist[v] holds the shortest path from src to every v.

When to Use Dijkstra

Why Dijkstra fails with negative edges

Once Dijkstra pops a node from the heap, it assumes: "this distance is final." With negative edges, a longer detour through a later-discovered node might swing back and become cheaper — but Dijkstra never revisits settled nodes. Use Bellman-Ford instead.

Watch Dijkstra Run

Dijkstra — shortest pathstime O((V+E) log V)space O(V)
425826327ABCDEFGH
priority queue:A:0
nodeABCDEFGH
dist0∞∞∞∞∞∞∞

1/19Dijkstra from A: dist[A] = 0, everything else ∞. Always settle the cheapest unsettled node next — greedy works because weights are non-negative.

start node

Complete Dijkstra Code

Python
import heapq

def dijkstra(adj, src, n):
    """adj[u] = list of (neighbor, weight). Returns dist array."""
    dist = [float('inf')] * n
    dist[src] = 0
    heap = [(0, src)]          # (distance, node)
    while heap:
        d, u = heapq.heappop(heap)
        if d > dist[u]: continue   # stale entry — skip!
        for v, w in adj[u]:
            if dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
                heapq.heappush(heap, (dist[v], v))
    return dist    # dist[i] = shortest distance from src to i

# LeetCode 743 — Network Delay Time
def networkDelayTime(times, n, k):
    adj = [[] for _ in range(n + 1)]
    for u, v, w in times:
        adj[u].append((v, w))
    dist = dijkstra(adj, k, n + 1)
    max_d = max(dist[1:])
    return max_d if max_d != float('inf') else -1
Java
int[] dijkstra(List<List<int[]>> adj, int src, int n) {
    int[] dist = new int[n];
    Arrays.fill(dist, Integer.MAX_VALUE);
    dist[src] = 0;
    // Min-heap: {distance, node}
    PriorityQueue<int[]> pq = new PriorityQueue<>(Comparator.comparingInt(a -> a[0]));
    pq.offer(new int[]{0, src});
    while (!pq.isEmpty()) {
        int[] cur = pq.poll();
        int d = cur[0], u = cur[1];
        if (d > dist[u]) continue;   // stale entry
        for (int[] edge : adj.get(u)) {
            int v = edge[0], w = edge[1];
            if (dist[u] + w < dist[v]) {
                dist[v] = dist[u] + w;
                pq.offer(new int[]{dist[v], v});
            }
        }
    }
    return dist;
}
C++
vector<int> dijkstra(vector<vector<pair<int,int>>>& adj, int src, int n) {
    vector<int> dist(n, INT_MAX);
    dist[src] = 0;
    // Min-heap: {distance, node}
    priority_queue<pair<int,int>, vector<pair<int,int>>, greater<>> pq;
    pq.push({0, src});
    while (!pq.empty()) {
        auto [d, u] = pq.top(); pq.pop();
        if (d > dist[u]) continue;   // stale
        for (auto [v, w] : adj[u]) {
            if (dist[u] + w < dist[v]) {
                dist[v] = dist[u] + w;
                pq.push({dist[v], v});
            }
        }
    }
    return dist;
}

Bellman-Ford — When Edges Go Negative

Why We Need Bellman-Ford

If a weighted graph has negative edge weights (think: a trade route where you gain money instead of spending it), Dijkstra breaks. Bellman-Ford handles this by brute-force relaxing every edge V-1 times.

Additionally, if there's a negative cycle (a loop whose total weight is negative), you could loop forever to keep reducing cost — Bellman-Ford can detect this.

Real-world: Currency arbitrage detection (can you make free money by converting currencies in a loop?), network routing with credits.

How to Approach (Relax All Edges V-1 Times)

  1. Initialize: dist[src] = 0, all others = ∞.
  2. Repeat V-1 times: For every edge (u, v, w), if dist[u] + w < dist[v], update dist[v].
    • After round k, all shortest paths using at most k edges are correct.
    • Since a simple path has at most V-1 edges, V-1 rounds are sufficient.
  3. Negative cycle check: Run one more round (round V). If anything updates, a negative cycle exists.

When to Use Bellman-Ford

  • Graph has negative edge weights
  • Need to detect a negative cycle
  • Problem has a hop limit (at most K edges) — just run K rounds instead of V-1
  • LeetCode 787: Cheapest Flights Within K Stops
Python
def bellman_ford(edges, V, src):
    """edges: list of (u, v, weight). Returns dist or raises if negative cycle."""
    dist = [float('inf')] * V
    dist[src] = 0
    for _ in range(V - 1):           # V-1 relaxation rounds
        updated = False
        for u, v, w in edges:
            if dist[u] != float('inf') and dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
                updated = True
        if not updated: break         # early exit: nothing changed

    # Negative cycle detection — V-th round
    for u, v, w in edges:
        if dist[u] != float('inf') and dist[u] + w < dist[v]:
            raise ValueError("Negative cycle detected!")
    return dist

# LeetCode 787 — Cheapest Flights Within K Stops (K+1 rounds)
def findCheapestPrice(n, flights, src, dst, k):
    dist = [float('inf')] * n
    dist[src] = 0
    for _ in range(k + 1):           # only k+1 rounds = at most k stops
        prev = dist[:]               # snapshot — prevents chaining hops in one round
        for u, v, price in flights:
            if prev[u] != float('inf') and prev[u] + price < dist[v]:
                dist[v] = prev[u] + price
    return -1 if dist[dst] == float('inf') else dist[dst]
Java
int[] bellmanFord(int n, int[][] edges, int src) {
    int[] dist = new int[n];
    Arrays.fill(dist, Integer.MAX_VALUE);
    dist[src] = 0;
    for (int i = 0; i < n - 1; i++) {
        boolean updated = false;
        for (int[] e : edges) {
            if (dist[e[0]] != Integer.MAX_VALUE && dist[e[0]] + e[2] < dist[e[1]]) {
                dist[e[1]] = dist[e[0]] + e[2];
                updated = true;
            }
        }
        if (!updated) break;   // early exit
    }
    // Negative cycle check
    for (int[] e : edges)
        if (dist[e[0]] != Integer.MAX_VALUE && dist[e[0]] + e[2] < dist[e[1]])
            dist[e[1]] = Integer.MIN_VALUE;   // mark as negative-cycle-affected
    return dist;
}
C++
vector<int> bellmanFord(int n, vector<tuple<int,int,int>>& edges, int src) {
    vector<int> dist(n, INT_MAX);
    dist[src] = 0;
    for (int i = 0; i < n - 1; i++) {
        bool updated = false;
        for (auto [u, v, w] : edges) {
            if (dist[u] != INT_MAX && dist[u] + w < dist[v]) {
                dist[v] = dist[u] + w;
                updated = true;
            }
        }
        if (!updated) break;
    }
    // Negative cycle detection
    for (auto [u, v, w] : edges)
        if (dist[u] != INT_MAX && dist[u] + w < dist[v])
            dist[v] = INT_MIN;
    return dist;
}

Floyd-Warshall — All-Pairs Shortest Paths

Why We Need Floyd-Warshall

Dijkstra gives shortest paths from one source. But what if you need shortest paths between every pair of nodes? Running Dijkstra V times works but is O(V · (V+E) log V). For small dense graphs, Floyd-Warshall's simple O(V³) 3-loop approach is often cleaner.

Real-world: Finding the shortest path between every pair of cities in a small region, finding the diameter of a network.

How to Approach (DP Over Intermediate Nodes)

This is a beautiful DP: dist[i][j] = shortest path from i to j using only nodes 0..k as intermediaries.

The outer loop variable k means: "you may now route through node k." For every pair (i, j), check if routing through k is shorter: dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]).

Critical rule: k must be the outermost loop — you unlock intermediaries one by one.

When to Use Floyd-Warshall

Python
def floyd_warshall(n, edges):
    """edges: list of (u, v, weight). Returns V×V distance matrix."""
    INF = float('inf')
    dist = [[INF] * n for _ in range(n)]
    for i in range(n): dist[i][i] = 0          # distance to self = 0
    for u, v, w in edges:
        dist[u][v] = min(dist[u][v], w)
        dist[v][u] = min(dist[v][u], w)         # remove for directed graph

    # k MUST be the outermost loop — unlock one intermediary at a time
    for k in range(n):
        for i in range(n):
            for j in range(n):
                if dist[i][k] + dist[k][j] < dist[i][j]:
                    dist[i][j] = dist[i][k] + dist[k][j]
    return dist

# After: dist[i][j] = shortest path from i to j (INF if unreachable)
# Negative cycle check: if dist[i][i] < 0 for any i → negative cycle exists
Java
int[][] floydWarshall(int n, int[][] edges) {
    final int INF = (int) 1e9;
    int[][] dist = new int[n][n];
    for (int[] row : dist) Arrays.fill(row, INF);
    for (int i = 0; i < n; i++) dist[i][i] = 0;
    for (int[] e : edges) {
        dist[e[0]][e[1]] = Math.min(dist[e[0]][e[1]], e[2]);
        dist[e[1]][e[0]] = Math.min(dist[e[1]][e[0]], e[2]);  // undirected
    }
    // k = the intermediary node unlocked this round
    for (int k = 0; k < n; k++)
        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++)
                if (dist[i][k] != INF && dist[k][j] != INF)
                    dist[i][j] = Math.min(dist[i][j], dist[i][k] + dist[k][j]);
    return dist;
}
C++
vector<vector<int>> floydWarshall(int n, vector<tuple<int,int,int>>& edges) {
    const int INF = 1e9;
    vector<vector<int>> dist(n, vector<int>(n, INF));
    for (int i = 0; i < n; i++) dist[i][i] = 0;
    for (auto [u, v, w] : edges) {
        dist[u][v] = min(dist[u][v], w);
        dist[v][u] = min(dist[v][u], w);   // remove for directed
    }
    for (int k = 0; k < n; k++)           // k = intermediary node
        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++)
                if (dist[i][k] != INF && dist[k][j] != INF)
                    dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
    return dist;
}

Minimum Spanning Trees (MST)

Why MST? — The Cabling Problem

You have 5 cities and need to connect all of them with roads so any city can reach any other. Each possible road has a construction cost. You want the minimum total cost to connect them all, without building any redundant roads (no cycles — a cycle means you built an unnecessary road).

That is the Minimum Spanning Tree problem: a tree that spans (connects) all V nodes using exactly V-1 edges with minimum total weight.

When to use MST:

  • "Connect all points at minimum cost" — LeetCode 1584: Min Cost to Connect All Points
  • Network design (power grids, pipelines)
  • Approximation algorithms (TSP approximation uses MST)

Two classic algorithms:

KruskalPrim
Think inEdges (global view)Nodes (grow one tree)
Data structureSort edges + Union-FindMin-heap
Best forSparse graphs, edge list givenDense graphs, adjacency list
ComplexityO(E log E)O((V+E) log V)

Kruskal's Algorithm

Intuition: Sort ALL edges by weight (cheapest first). Walk through them one by one. Add an edge if it connects two different components (doesn't form a cycle). Stop when you have V-1 edges. Union-Find checks "same component?" in near-O(1).

Python
def kruskal(n, edges):
    """edges: list of (weight, u, v). Returns minimum spanning tree weight."""
    edges.sort()    # sort by weight — cheapest first
    parent = list(range(n))
    rank = [0] * n

    def find(x):
        if parent[x] != x:
            parent[x] = find(parent[x])    # path compression
        return parent[x]

    def union(x, y):
        rx, ry = find(x), find(y)
        if rx == ry: return False           # same component — would form cycle
        if rank[rx] < rank[ry]: rx, ry = ry, rx
        parent[ry] = rx
        if rank[rx] == rank[ry]: rank[rx] += 1
        return True

    mst_weight = 0
    edges_used = 0
    for w, u, v in edges:
        if union(u, v):
            mst_weight += w
            edges_used += 1
            if edges_used == n - 1: break   # MST complete
    return mst_weight
Java
int kruskal(int n, int[][] edges) {
    // edges[i] = {weight, u, v}
    Arrays.sort(edges, Comparator.comparingInt(e -> e[0]));
    int[] parent = new int[n], rank = new int[n];
    for (int i = 0; i < n; i++) parent[i] = i;

    int mstWeight = 0, edgeCount = 0;
    for (int[] e : edges) {
        int pu = find(parent, e[1]), pv = find(parent, e[2]);
        if (pu != pv) {
            if (rank[pu] < rank[pv]) { int t = pu; pu = pv; pv = t; }
            parent[pv] = pu;
            if (rank[pu] == rank[pv]) rank[pu]++;
            mstWeight += e[0];
            if (++edgeCount == n - 1) break;
        }
    }
    return mstWeight;
}

int find(int[] parent, int x) {
    return parent[x] == x ? x : (parent[x] = find(parent, parent[x]));
}
C++
struct UnionFind {
    vector<int> parent, rank;
    UnionFind(int n) : parent(n), rank(n, 0) {
        iota(parent.begin(), parent.end(), 0);
    }
    int find(int x) {
        return parent[x] == x ? x : parent[x] = find(parent[x]);
    }
    bool unite(int x, int y) {
        x = find(x); y = find(y);
        if (x == y) return false;
        if (rank[x] < rank[y]) swap(x, y);
        parent[y] = x;
        if (rank[x] == rank[y]) rank[x]++;
        return true;
    }
};

int kruskal(int n, vector<tuple<int,int,int>>& edges) {
    sort(edges.begin(), edges.end());   // sort by weight (first element of tuple)
    UnionFind uf(n);
    int mstWeight = 0, edgesUsed = 0;
    for (auto [w, u, v] : edges) {
        if (uf.unite(u, v)) {
            mstWeight += w;
            if (++edgesUsed == n - 1) break;
        }
    }
    return mstWeight;
}

Prim's Algorithm

Intuition: Start at any node. Grow one tree outward by always picking the cheapest edge that connects the current tree to a new node outside it. Uses a min-heap exactly like Dijkstra — but you track edge weights, not total distances from source.

Python
import heapq

def prim(adj, n):
    """adj[u] = list of (neighbor, weight). Returns MST total weight."""
    visited = [False] * n
    heap = [(0, 0)]     # (edge_cost, node) — start at node 0 with cost 0
    mst_weight = 0
    while heap:
        cost, u = heapq.heappop(heap)
        if visited[u]: continue     # already in the tree
        visited[u] = True
        mst_weight += cost
        for v, w in adj[u]:
            if not visited[v]:
                heapq.heappush(heap, (w, v))    # push EDGE WEIGHT, not total dist
    return mst_weight
Java
int prim(List<List<int[]>> adj, int n) {
    boolean[] visited = new boolean[n];
    PriorityQueue<int[]> pq = new PriorityQueue<>(Comparator.comparingInt(a -> a[0]));
    pq.offer(new int[]{0, 0});   // {edge_cost, node}
    int mstWeight = 0;
    while (!pq.isEmpty()) {
        int[] cur = pq.poll();
        int cost = cur[0], u = cur[1];
        if (visited[u]) continue;
        visited[u] = true;
        mstWeight += cost;
        for (int[] edge : adj.get(u))
            if (!visited[edge[0]])
                pq.offer(new int[]{edge[1], edge[0]});   // {weight, neighbor}
    }
    return mstWeight;
}
C++
int prim(vector<vector<pair<int,int>>>& adj, int n) {
    vector<bool> visited(n, false);
    priority_queue<pair<int,int>, vector<pair<int,int>>, greater<>> pq;
    pq.push({0, 0});   // {edge_cost, node}
    int mstWeight = 0;
    while (!pq.empty()) {
        auto [cost, u] = pq.top(); pq.pop();
        if (visited[u]) continue;
        visited[u] = true;
        mstWeight += cost;
        for (auto [v, w] : adj[u])
            if (!visited[v])
                pq.push({w, v});   // push EDGE WEIGHT, not cumulative dist
    }
    return mstWeight;
}
Prim vs Dijkstra — Same Shape, Different Meaning

Both use a min-heap and a "visited" array. The difference is what you push to the heap:

  • Dijkstra: push(total_distance_from_source, node) — minimizes cumulative path cost
  • Prim: push(edge_weight, node) — minimizes the cost of the single edge that adds this node to the tree

Same skeleton, different semantics. If you understand one, you understand both.

Think it Through — Cheapest Flights Within K Stops

Think it through: Cheapest Flights Within K StopsMedium — LeetCode 787 (Amazon, Uber)0/3 stages

PROBLEMFind the cheapest price from src to dst using at most K stops, in a weighted directed graph of flights. Return -1 if impossible.

  1. 1

    Why plain Dijkstra is wrong

    “Dijkstra finds the cheapest path — so what does the 'at most K stops' constraint break?”

  2. 2

    The Bellman-Ford insight

    “How does Bellman-Ford's round structure naturally handle the hop limit?”

    unlocks after the stage above
  3. 3

    The snapshot subtlety

    “In each Bellman-Ford round, why MUST you work from a copy of last round's distances?”

    unlocks after the stage above

Check Yourself

Check yourself0/4 answered

1. You have a weighted directed graph with some negative edges but no negative cycles. Which algorithm finds single-source shortest paths?

2. Floyd-Warshall has 3 nested loops. What does the OUTERMOST loop variable k represent?

3. Kruskal uses Union-Find. What question does Union-Find answer during edge selection?

4. Prim's algorithm and Dijkstra's algorithm use the same heap-based structure. What is different?

Practice — Climb the Ladder

Practice ladder: Advanced Graphs — Weighted Shortest Paths & MST0/11 solved

Climb in order — every rung assumes the one above it. Solve on LeetCode, then tick it here; progress is saved on this device.

Level 1 — Dijkstra Basics

vanilla single-source shortest path
  1. Network Delay TimeMedium

    Classic Dijkstra — single source, non-negative weights; answer is max(dist).

  2. Path With Minimum EffortMedium

    Dijkstra where 'dist' = max edge on the path, not total — redefine the metric.

  3. Path with Maximum ProbabilityMedium

    Max-heap Dijkstra — multiply probabilities, flip to max; same template.

Level 2 — Constrained Shortest Path

Bellman-Ford when Dijkstra can't help
  1. Cheapest Flights Within K StopsMedium

    Bellman-Ford with K+1 rounds + prev[] snapshot — the hop-limit classic.

  2. Minimum Cost to Reach Destination in TimeHard

    State is (node, time) — 2D Dijkstra / BFS with bounded time.

Level 3 — MST

connect all nodes at minimum cost
  1. Min Cost to Connect All PointsMedium

    Prim's or Kruskal's MST on a complete graph — Manhattan distance as weights.

  2. Swim in Rising WaterHard

    Dijkstra where cost = max cell value on path; or Binary Search + BFS/Union-Find.

  3. Find Critical and Pseudo-Critical Edges in MSTHard

    Kruskal MST + forced-inclusion / forced-exclusion to classify each edge.

Level 4 — All-Pairs & Advanced Modeling

Floyd-Warshall and graph modeling challenges
  1. Find the City With Smallest Neighbors at ThresholdMedium

    Floyd-Warshall all-pairs, then count neighbors within threshold per city.

  2. Reconstruct ItineraryHard

    Eulerian path (Hierholzer's algorithm) — every edge used exactly once.

  3. Bus RoutesHard

    BFS on routes (not stops) — the modeling insight IS the problem.