Weighted Graphs: Shortest Paths and Spanning Trees

Weighted graphs

In plain words: a weighted graph is a map where every road has a number written on it — its length, its travel time or its price. The "shortest" route is now the one with the smallest total number, not the one with the fewest roads.

In a weighted graph every edge carries a number: a distance, a travel time, a cost. The length of a path is now the sum of its weights, not the number of edges, so BFS from the previous chapter no longer finds shortest paths: a 3-edge path of total weight 4 beats a 1-edge path of weight 10.

      A ------(10)------ D           BFS picks A → D (1 edge, cost 10)
      |                  |           but A → B → C → D costs 1 + 2 + 1 = 4
     (1)                (1)
      |                  |
      B ------(2)------- C

Store the weight next to the neighbour in the adjacency lists:

List<List<int[]>> adj = new ArrayList<>();          // adj.get(u) holds {v, w} pairs
for (int i = 0; i < n; i++) adj.add(new ArrayList<>());
adj.get(u).add(new int[]{v, w});                     // directed edge u -> v with weight w
adj.get(v).add(new int[]{u, w});                     // add this too if the graph is undirected

(A small Edge class with to and weight fields reads better in larger programs; an adjacency matrix can store the weights directly, with a sentinel for "no edge".)

Relaxation

All shortest-path algorithms keep an estimate dist[v] — the best distance from the source s found so far — starting at 0 for s and ∞ for everything else. Improving an estimate through one edge is called relaxing the edge u → v:

if (dist[u] + w < dist[v]) {     // going through u is better than what we knew
    dist[v] = dist[u] + w;
    pred[v] = u;                 // remember how we got here
}

For example, with dist[u] = 3, w = 2 and dist[v] = 10: 3 + 2 = 5 < 10, so dist[v] becomes 5 and pred[v] becomes u. If dist[v] had been 4, nothing would change, because 5 is not better than 4.

The algorithms differ only in which edges they relax, and in what order.

Dijkstra's algorithm

Dijkstra's algorithm grows a set of settled vertices whose distance is final. At each step it settles the unsettled vertex with the smallest dist and relaxes all its outgoing edges.

Why is the smallest one final? Any other route to it must leave the settled set through some unsettled vertex x with dist[x] ≥ dist[u], and with non-negative weights the rest of that route cannot make it shorter again.

A priority queue finds the smallest estimate quickly. Java's PriorityQueue has no "decrease key", so we use lazy deletion: push a new entry whenever a distance improves, and skip outdated entries when they come out.

static long[] dijkstra(List<List<int[]>> adj, int s, int[] pred) {
    int n = adj.size();
    long[] dist = new long[n];
    Arrays.fill(dist, Long.MAX_VALUE);
    Arrays.fill(pred, -1);
    dist[s] = 0;
    PriorityQueue<long[]> pq = new PriorityQueue<>((a, b) -> Long.compare(a[0], b[0]));
    pq.add(new long[]{0, s});                       // {distance, vertex}
    while (!pq.isEmpty()) {
        long[] top = pq.poll();
        int u = (int) top[1];
        if (top[0] > dist[u]) continue;             // stale entry: u already settled
        for (int[] e : adj.get(u)) {
            int v = e[0];
            if (dist[u] + e[1] < dist[v]) {         // relax u -> v
                dist[v] = dist[u] + e[1];
                pred[v] = u;
                pq.add(new long[]{dist[v], v});
            }
        }
    }
    return dist;
}

Each successful relaxation adds one entry, so the queue sees at most E + 1 insertions, each O(log E) = O(log V). Total: O((V + E) log V). Without a heap — scanning an array for the minimum — each of the V steps costs O(V), giving O(V²), which is actually better for dense graphs where E ≈ V².

Tracing by hand. Keep a table with one column per vertex and one row per settled vertex. On graph H below, from 0:

0: (3, 2)  (4, 7)          3: (1, 8)  (4, 3)  (5, 10)
1: (2, 6)  (5, 2)          4: (1, 1)  (2, 12)
2:                         5: (2, 3)

(Each pair is (neighbour, weight) of a directed edge: 0: (3, 2) means 0 → 3 with weight 2.)

settle	d0	d1	d2	d3	d4	d5
start	0	∞	∞	∞	∞	∞
0	0	∞	∞	2	7	∞
3		10	∞	2	5	12
4		6	17		5	12
1		6	12			8
5			11			8
2			11

Notice that d4 dropped from 7 to 5 and d2 dropped three times before being settled: an estimate can improve many times, but once a vertex is settled it never changes.

The same run, step by step, with the priority queue. Entries are (distance, vertex), listed smallest first. (Produced by running the code above.)

Step	Poll	Relaxations (old → new)	dist[0..5] after	Queue after
start			0 ∞ ∞ ∞ ∞ ∞	(0,0)
1	(0,0): settle 0	d3 ∞→2, d4 ∞→7	0 ∞ ∞ 2 7 ∞	(2,3) (7,4)
2	(2,3): settle 3	d1 ∞→10, d4 7→5, d5 ∞→12	0 10 ∞ 2 5 12	(5,4) (7,4) (10,1) (12,5)
3	(5,4): settle 4	d1 10→6, d2 ∞→17	0 6 17 2 5 12	(6,1) (7,4) (10,1) (12,5) (17,2)
4	(6,1): settle 1	d2 17→12, d5 12→8	0 6 12 2 5 8	(7,4) (8,5) (10,1) (12,2) (12,5) (17,2)
5	(7,4): stale (7 > d4 = 5), skip		unchanged	(8,5) (10,1) (12,2) (12,5) (17,2)
6	(8,5): settle 5	d2 12→11	0 6 11 2 5 8	(10,1) (11,2) (12,2) (12,5) (17,2)
7	(10,1): stale, skip		unchanged	(11,2) (12,2) (12,5) (17,2)
8	(11,2): settle 2	(no out-edges)	0 6 11 2 5 8	(12,2) (12,5) (17,2)
9–11	three stale entries, skipped		final	empty

Settling order: 0, 3, 4, 1, 5, 2 — always in increasing distance (0, 2, 5, 6, 8, 11). The old entries (7,4), (10,1), (12,2), (12,5) and (17,2) are the price of lazy deletion: they stay in the heap until they are polled and thrown away.

Rebuilding the path

In plain words: each vertex remembers only "who sent me here" (its predecessor). To get the whole route to t, ask t who sent it, ask that vertex who sent it, and so on back to the source — then read the answers backwards.

pred[v] is the vertex just before v on the best path found. Walk back from the target and reverse, exactly as with the BFS parent array:

Deque<Integer> path = new ArrayDeque<>();
for (int v = t; v != -1; v = pred[v]) path.push(v);

For H, pred = [−1, 4, 5, 0, 3, 1], so the path to 2 is 0 → 3 → 4 → 1 → 5 → 2 (2 + 3 + 1 + 2 + 3 = 11). The pred pointers of all vertices together form the shortest-path tree rooted at s.

Walking back from 2: pred[2] = 5, pred[5] = 1, pred[1] = 4, pred[4] = 3, pred[3] = 0, pred[0] = −1 (stop). Collected backwards: 2, 5, 1, 4, 3, 0; reversed: 0, 3, 4, 1, 5, 2.

shortest-path tree of H from 0:

        0
        |  2
        3
        |  3
        4
        |  1
        1
        |  2
        5
        |  3
        2

(Here the tree happens to be a single path; in general it branches.)

Negative weights and Bellman–Ford

In plain words: Dijkstra trusts that "a longer walk can never become cheaper later". A negative edge is like a road that pays you to drive on it — then a long detour can end up cheaper than the direct route, and Dijkstra's "this vertex is final" promise is broken.

Dijkstra settles a vertex assuming nothing found later can beat it. A negative edge breaks that promise:

0 -> 1 (2)    0 -> 2 (5)    2 -> 1 (-4)

Dijkstra settles 1 with distance 2, then settles 2 (5) — but 0 → 2 → 1 costs 5 − 4 = 1. Vertex 1 is already final, so the answer 2 is wrong.

Bellman–Ford makes no such promise. It simply relaxes every edge, in any fixed order, V − 1 times:

for (int round = 1; round <= n - 1; round++) {
    for (int[] e : edges) {                          // e = {u, v, w}
        if (dist[e[0]] != INF && dist[e[0]] + e[2] < dist[e[1]]) {
            dist[e[1]] = dist[e[0]] + e[2];
        }
    }
}

A shortest path has at most V − 1 edges, and after round k every shortest path with at most k edges is correct, so V − 1 rounds suffice. If a V-th round still improves some distance, the graph has a negative cycle reachable from s, and "shortest path" is undefined (you could loop forever). Cost: O(V · E) — much slower than Dijkstra, so use it only when negative edges are possible.

Worked example 1 — the graph above, edges relaxed in the order listed (0→1, 0→2, 2→1):

After	d0	d1	d2	Why
start	0	∞	∞
round 1	0	1	5	0→1 gives 2, 0→2 gives 5, then 2→1 gives 5 − 4 = 1
round 2	0	1	5	no change — the answer d1 = 1 is correct

Worked example 2 — why V − 1 rounds. Path 0 → 1 → 2 → 3, every weight 1, but the edges are listed in the worst order: 2→3, 1→2, 0→1.

After	d0	d1	d2	d3
start	0	∞	∞	∞
round 1	0	1	∞	∞
round 2	0	1	2	∞
round 3 = V − 1	0	1	2	3
round 4	no change

In each round the correct distance moves only one edge further along the path, so a path with V − 1 edges needs V − 1 rounds.

Worked example 3 — a negative cycle. Edges 0→1 (1), 1→2 (−1), 2→1 (−1); the cycle 1 → 2 → 1 has total weight −2. With V = 3:

After	d0	d1	d2
round 1	0	−1	0
round 2 = V − 1	0	−3	−2
round 3 = V (the check)	0	−5	−4

Round V still improves the distances, so Bellman–Ford reports a negative cycle. Every extra trip around the cycle would lower them by 2 more.

Minimum spanning trees

A spanning tree of a connected undirected graph is a subset of its edges that connects all V vertices without a cycle — it always has exactly V − 1 edges. A minimum spanning tree (MST) is one with the smallest total weight: the cheapest way to connect every town with cable. If the graph is not connected, the best you can do is a minimum spanning forest, one tree per component.

The Prim and Kruskal examples below use this undirected graph M (6 villages, 8 possible cables, weights in brackets):

   0 ---(4)--- 1
   |         / |
  (3)    (1)  (2)
   |   /       |
   2 ---(4)--- 3 ---(2)--- 4
               |           |
              (5)         (6)
               |           |
               +---- 5 ----+

 edges: 0-1 (4), 0-2 (3), 1-2 (1), 1-3 (2), 2-3 (4), 3-4 (2), 3-5 (5), 4-5 (6)

The key fact is the cut property. Split the vertices into any two non-empty groups (a cut). The lightest edge crossing the cut belongs to some MST (to every MST if it is the unique lightest). Reason: if an MST T avoided that edge e, adding e to T creates a cycle, which must cross the cut a second time through some edge f with weight ≥ w(e); swapping f for e gives a spanning tree no heavier than T.

For example, in M cut {5} away from the rest: the crossing edges are 3-5 (5) and 4-5 (6). The lightest, 3-5, must be in the MST — village 5 has to be connected somehow, and 3-5 is the cheapest way.

If all edge weights are distinct, the MST is unique.

Prim's algorithm

In plain words: start in one village and grow the network outwards. At each step, look at all cables that go from a connected village to an unconnected one, and build the cheapest. Repeat until every village is connected.

Prim grows one tree from a start vertex. At each step the tree and the rest of the graph form a cut, and Prim adds the lightest edge crossing it (cut property). With a priority queue of (weight, vertex) entries and lazy deletion, the code looks almost like Dijkstra's — the only difference is the key: the weight of the single edge into the tree, not the distance from the source.

boolean[] inTree = new boolean[n];
PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> Integer.compare(a[0], b[0]));
pq.add(new int[]{0, 0});                          // {edge weight, vertex}
long total = 0;
while (!pq.isEmpty()) {
    int[] top = pq.poll();
    int u = top[1];
    if (inTree[u]) continue;                      // stale entry
    inTree[u] = true;
    total += top[0];
    for (int[] e : adj.get(u)) {
        if (!inTree[e[0]]) pq.add(new int[]{e[1], e[0]});
    }
}

Worked example — Prim on M from 0. Queue entries are (edge weight, vertex), smallest first; ties would be broken by the smaller vertex, but none occurs at a decision point here.

Step	Poll	Added to tree (via edge)	Total	Queue after
1	(0,0)	0 (start)	0	(3,2) (4,1)
2	(3,2)	2 via 0-2	3	(1,1) (4,1) (4,3)
3	(1,1)	1 via 2-1	4	(2,3) (4,1) (4,3)
4	(2,3)	3 via 1-3	6	(2,4) (4,1) (4,3) (5,5)
5	(2,4)	4 via 3-4	8	(4,1) (4,3) (5,5) (6,5)
6	(4,1), (4,3)	stale: 1 and 3 are already in the tree	8	(5,5) (6,5)
7	(5,5)	5 via 3-5	13	(6,5), later skipped as stale

MST edges: 0-2, 1-2, 1-3, 3-4, 3-5 — five edges (V − 1 = 5), total weight 13.

   0           1
   |         / |
  (3)    (1)  (2)
   |   /       |
   2           3 ---(2)--- 4
               |
              (5)
               |
               5

Notice step 3: vertex 1 first entered the queue with key 4 (the edge 0-1), but a cheaper edge 2-1 (1) was found later. Prim uses the weight of the one edge that connects a vertex to the tree — it never adds up distances.

Cost O(E log V) with a heap; O(V²) with an array, again the better choice for dense graphs.

Kruskal's algorithm and union–find

Kruskal builds a forest: sort all edges by weight and take each edge unless it would join two vertices that are already connected (that would close a cycle). Each accepted edge is the lightest edge crossing the cut between its endpoint's component and the rest, so the cut property again guarantees correctness.

The question "are u and v already connected?" is answered by a union–find (disjoint-set) structure. Every set is a tree stored in a parent array; the root names the set.

int find(int x) {
    if (parent[x] != x) parent[x] = find(parent[x]);   // path compression
    return parent[x];
}

boolean union(int a, int b) {
    int ra = find(a), rb = find(b);
    if (ra == rb) return false;                        // same set already
    if (size[ra] < size[rb]) { int t = ra; ra = rb; rb = t; }
    parent[rb] = ra;                                   // union by size: small under big
    size[ra] += size[rb];
    return true;
}

(At the start parent[i] = i and size[i] = 1 for every i: each vertex is its own set. When the two sizes are equal, this code keeps a's root as the root.)

• Union by size (or by rank, an upper bound on height) always hangs the smaller tree under the larger root, so tree height stays O(log n).
• Path compression makes every vertex on the find path point straight at the root, so later finds are almost free.
• Together, any sequence of m operations costs O(m · α(n)), where α is the inverse Ackermann function — at most 4 for any n you will ever meet. In practice, near-constant amortized time per operation.

Without either trick, unions can build a chain and a single find costs O(n).

Worked example — Kruskal on M. The edges sorted by weight (ties broken by the smaller endpoints, so 1-3 comes before 3-4, and 0-1 before 2-3). parent and size are shown after each edge; only the root's size entry is meaningful.

Edge	find(u), find(v)	Decision	parent[0..5] after	size of root	Total
start			0 1 2 3 4 5	all 1	0
1-2 (1)	1, 2	take: union → parent[2] = 1	0 1 1 3 4 5	size[1] = 2	1
1-3 (2)	1, 3	take: parent[3] = 1	0 1 1 1 4 5	size[1] = 3	3
3-4 (2)	1, 4	take: parent[4] = 1	0 1 1 1 1 5	size[1] = 4	5
0-2 (3)	0, 1	take: size 1 < 4, so the root 0 goes under 1	1 1 1 1 1 5	size[1] = 5	8
0-1 (4)	1, 1	reject: same set, would make a cycle	unchanged		8
2-3 (4)	1, 1	reject	unchanged		8
3-5 (5)	1, 5	take: parent[5] = 1	1 1 1 1 1 1	size[1] = 6	13

Five edges taken (V − 1), so Kruskal stops; 4-5 (6) is never examined. The MST has weight 13 and uses the same five edges that Prim chose (the MST of M is unique). In general Prim and Kruskal always find trees of the same total weight; when some weights are equal they may pick different edges.

Worked example — path compression. Six elements, starting with parent = [0, 1, 2, 3, 4, 5]:

Operation	parent[0..5] after	Note
union(0, 1)	0 0 2 3 4 5	equal sizes: 1 goes under 0
union(2, 3)	0 0 2 2 4 5	3 goes under 2
union(4, 5)	0 0 2 2 4 4	5 goes under 4
union(0, 2)	0 0 0 2 4 4	sizes 2 and 2: root 2 goes under root 0
union(5, 3)	0 0 0 0 0 4	find(3) walks 3 → 2 → 0 and compresses: parent[3] = 0. Then root 4 (size 2) goes under root 0 (size 4)
find(5)	0 0 0 0 0 0	walks 5 → 4 → 0 and compresses: parent[5] = 0

before find(5):          after find(5):

        0                        0
      / | \ \               / / | \ \
     1  2  3  4            1 2  3  4  5
              |
              5

After these compressions every element points straight at the root, so the next find on any of them takes one step.

Kruskal's total cost is dominated by sorting: O(E log E) = O(E log V).

	Prim	Kruskal
grows	one tree from a start vertex	a forest that merges
needs	adjacency lists + priority queue	edge list + sort + union–find
cost	O(E log V) (heap), O(V²) (array)	O(E log E)
good for	dense graphs (array version)	sparse graphs, edges already sorted

MST vs shortest-path tree

In plain words: the cable company wants the cheapest network in total. A delivery driver leaving one depot wants the quickest route to each customer. These are different goals, so they usually lead to different trees.

Both are spanning trees, but they minimise different things. The MST minimises the total weight of the tree. The shortest-path tree from s minimises each vertex's distance from s. Take the triangle 0–1 (2), 1–2 (2), 0–2 (3):

   the graph            MST (total 4)        shortest-path tree from 0 (total 5)

       0                     0                        0
      / \                   /                        / \
   (2)   (3)             (2)                      (2)   (3)
    /     \               /                        /     \
   1--(2)--2             1--(2)--2                1       2

• MST: {0–1, 1–2}, total 4. The distance from 0 to 2 inside it is 4.
• Shortest-path tree from 0: {0–1, 0–2}, total 5, but 2 is at distance 3.

Neither tree is "better": a cable network wants the MST; a delivery service leaving a single depot wants the shortest-path tree. The shortest-path tree also depends on the source; the MST does not.

Key takeaways

• In a weighted graph a path's length is the sum of its weights; BFS no longer gives shortest paths.
• Relaxation (dist[u] + w < dist[v] → update dist[v] and pred[v]) is the building block of every shortest-path algorithm.
• Dijkstra settles vertices in increasing distance order; a settled distance is final only if all weights are ≥ 0. With a heap and lazy deletion it costs O((V + E) log V); skip stale queue entries.
• Bellman–Ford relaxes every edge V − 1 times (O(VE)), works with negative edges, and detects a negative cycle when round V still improves something.
• An MST connects all V vertices with V − 1 edges and minimum total weight. The cut property makes Prim (grow one tree, cheapest edge into it) and Kruskal (cheapest edges overall, skip cycles) correct.
• Union–find: find returns the root (the "president"); union joins roots, smaller under larger; path compression flattens trees. Nearly O(1) amortized per operation.
• MST ≠ shortest-path tree: the first minimises the total, the second each distance from the source.