Weighted graphs: minimum spanning tree and shortest path

← Back to the section

In an ordinary graph an edge is either there or not. In real life, though, a connection has a price: a road is longer or shorter, a cable is cheaper or more expensive. Once edges carry numbers — weights — the graph becomes weighted, and two classic problems appear: connect everything cheaply, and get there fast.

Minimum spanning tree

The problem: there are towns, some pairs can be linked by a cable, and every line has its own cost. All towns must be connected so that the total cost is the smallest possible. The answer is the minimum spanning tree (MST): a set of edges that connects every vertex, has no cycles, and has the smallest sum of weights.

It is built greedily — this way of doing it is known as Prim's algorithm. Start from one vertex and at each step add the cheapest edge leading from the already-connected part to a vertex that is not connected yet, until all of them are in. The locally cheapest choice here is what produces the global minimum. To find that cheapest edge quickly, a priority queue is used. This is how networks get designed: cable, road, electrical.

Shortest path: Dijkstra's algorithm

The other problem is not "connect everything" but "get from A to B as fast as possible": find the shortest route over roads of known length. The classic solution is Dijkstra's algorithm.

For every vertex we keep the best known distance from the start; at the beginning it is 0 for the start and "infinity" for the rest. At each step you take the nearest vertex that has not been processed yet and "relax" its neighbours: if going through it makes the distance to a neighbour shorter than what was known, that distance is updated. A processed vertex is never touched again — its shortest distance is already final. Repeat until every vertex has been processed.

The analogy is water spreading from a source: it reaches the nearest points first, and every point by the shortest route. To pick the "nearest unprocessed vertex" quickly each time, Dijkstra leans on a priority queue — the same heap. Hence navigators and network routing. One important caveat: classic Dijkstra requires edge weights to be non-negative.

The same graph in code. The program prints the order in which Dijkstra pulls vertices out of the queue: strictly by increasing distance — and B gets processed even though it is not on the shortest path.

live example

import java.util.*;

public class Dijkstra {
    public static void main(String[] args) {
        String[] name = {"S", "A", "B", "C", "T"};
        int[][] edges = {{0, 1, 2}, {0, 2, 5}, {1, 3, 2}, {3, 4, 3}, {2, 4, 4}};
        int[][] w = new int[name.length][name.length];
        for (int[] e : edges) { w[e[0]][e[1]] = e[2]; w[e[1]][e[0]] = e[2]; }
        int[] dist = new int[name.length];
        Arrays.fill(dist, Integer.MAX_VALUE);
        dist[0] = 0;
        Queue<int[]> frontier = new PriorityQueue<>(Comparator.comparingInt(pair -> pair[1]));
        frontier.add(new int[]{0, 0});
        System.out.print("processing order: ");
        while (!frontier.isEmpty()) {
            int[] cur = frontier.poll();
            if (cur[1] > dist[cur[0]]) continue;
            System.out.print(name[cur[0]] + "(" + cur[1] + ") ");
            for (int v = 0; v < name.length; v++) {
                if (w[cur[0]][v] == 0) continue;
                int viaCur = cur[1] + w[cur[0]][v];
                if (viaCur < dist[v]) {
                    dist[v] = viaCur;
                    frontier.add(new int[]{v, viaCur});
                }
            }
        }
        System.out.println("\nreached T at " + dist[4]);
    }
}

The "every vertex to every vertex" table — shortest paths between all pairs — is built not by Dijkstra but by the Floyd–Warshall algorithm.

When a problem is intractable

Weighted graphs also lead to problems that look similar yet are incomparably harder. The most famous is the travelling salesman problem: find the shortest route that visits every town exactly once and returns to the start. It looks a notch harder than the shortest path — but no fast exact algorithm for it is known: the number of options grows factorially, and for a large number of towns brute force cannot finish in any reasonable time.

Such problems are called intractable; theory gives them names. NP-complete covers yes/no questions such as "does a Hamiltonian cycle exist", and NP-hard covers the travelling salesman, where the question is not "is there a route" but "which of them is cheapest". The acronyms do not matter, the consequence does: in practice nobody looks for the perfect answer — a good-enough route produced by heuristics will do.

How it is done in Java

Neither Dijkstra nor the minimum spanning tree ships with the standard library — those algorithms are written by hand. The priority queue both of them rest on, however, does not need writing: it is java.util.PriorityQueue.

Inside PriorityQueue is exactly the binary heap laid out in an array. Hence the honest complexities: offer (put in) and poll (take the minimum) are O(log N) for the sift up and the sift down, while peek (look at the minimum without removing it) and size are O(1). The order comes from the comparator passed to the constructor — in the example above that is Comparator.comparingInt(pair -> pair[1]), meaning "by distance".

The real trap is in Dijkstra itself. The textbook algorithm needs an operation "decrease the distance of a vertex that is already in the queue", and PriorityQueue has no such operation. Changing a field of an object that is already inside does not work either: the heap will not notice the change and its order breaks. remove(Object) does exist, but it finds the element by a linear scan in O(N), which eats the entire gain. So in practice the queue is not edited but appended to: when a shorter path is found, a new "vertex, distance" pair is pushed, and when a stale copy surfaces it is simply skipped after checking the distance against the table of the best ones. That is what the line if (cur[1] > dist[cur[0]]) continue; does in the example above. The queue swells to the number of edges, but the time stays O(E·log V). If a genuine decrease-key really is needed, a TreeSet of "distance, vertex" pairs on a red-black tree is used instead of the heap: there an element can be found and removed in O(log N).

In short

• In a weighted graph edges carry a number (cost, length, time), and optimisation problems appear.
• The minimum spanning tree (MST) connects every vertex with the smallest sum of weights; greedy Prim's algorithm keeps adding the cheapest edge to the already-connected part.
• Dijkstra's algorithm finds the shortest path from the start: it processes vertices in order of nearness, updating the distances of neighbours; it leans on a priority queue and requires non-negative weights.
• Java's PriorityQueue cannot decrease a priority: stale pairs are appended rather than edited and skipped on removal — O(E·log V). When the real operation is needed, a TreeSet is used.
• The travelling salesman and Hamiltonian cycles are intractable: no fast exact algorithm exists, so they are solved approximately. Recognising such a problem early matters — brute force is doomed.

What to read next

• Graphs — breadth-first and depth-first traversal, where every graph algorithm starts.
• Heaps — how the priority queue that carries both Dijkstra and the spanning tree is built.
• Red-black trees — TreeSet, for when the queue lacks a decrease-key operation.
• Choosing a data structure — the section summary: what to take for which job.