Past exam of the year 1 of the computer science course of the University of Oxford / 2003 / Functional programming, data structures and algorithms, procedural programming, and digital hardware / 5

A greedy algorithm builds a feasible solution by repeatedly making the locally preferred available choice, committing to that choice without reconsidering earlier choices. “Preferred” must be specified by the problem's rule, such as choosing the cheapest eligible edge.

Local preference alone does not prove global optimality. A correctness argument needs a property ensuring that some optimum extends the choices already made, often proved by an exchange argument. Thus the distinguishing rule is

For a connected weighted undirected graph, Kruskal's algorithm begins with each vertex as a separate component and no selected edges. Sort all edges into nondecreasing weight order. Inspect them in that order and add an edge exactly when its endpoints lie in different current components. Merge those components after an addition; stop once $|V|-1$ edges have been accepted. A disjoint-set data structure implements the component tests and merges.

The accepted edges always form a forest, because an edge whose endpoints were already connected is rejected. To prove optimality, use the invariant that some minimum spanning tree contains every accepted edge. It holds initially. Suppose the next accepted edge is $e=uv$, and let $T$ be a minimum spanning tree extending the current forest. If $e\in T$, nothing changes. Otherwise adding $e$ to $T$ makes a unique graph cycle. The graph path from $u$ to $v$ in $T$ must cross the graph cut between the current component of $u$ and the remaining vertices, so that graph cycle contains an edge $f$ crossing this graph cut. No accepted edge crosses it. Furthermore $w(e)\le w(f)$: any strictly lighter crossing edge would already have been processed and accepted, since its endpoints could not then have been connected without also being connected now.

Replace $f$ by $e$. The resulting spanning tree still contains all previously accepted edges and has cost at most that of $T$, so it too is a minimum spanning tree. This is the exchange argument establishing the invariant. At termination the selected edges themselves form a spanning tree, henceEqual weights cause no difficulty; they may give several optima. On a disconnected graph, processing all edges instead returns a minimum spanning forest. Sorting costs $O(|E|\log |E|)$, with near-linear additional cost using an efficient disjoint-set data structure.

Use the DAG shortest-path algorithm: first compute a topological ordering, then perform edge relaxation once for every edge in that order. Store a shortest-path predecessor when a distance improves so that the actual paths, as well as their costs, can be recovered.

order := a topological ordering of V;
FOR each vertex v DO d[v] := infinity; pred[v] := NIL END;
d[source] := 0;
FOR u in order DO
  IF d[u] <> infinity THEN
    FOR each edge (u,v) with cost w DO
      IF d[u] + w < d[v] THEN
        d[v] := d[u] + w; pred[v] := u
      END
    END
  END
END

Each loop has a natural invariant. During initialization, all vertices already processed have infinite distance and no predecessor. During the outer relaxation loop, all processed vertices have their final shortest-path distances, and every edge leaving a processed vertex has been relaxed. During an inner edge loop, the outgoing edges of u already inspected have been relaxed using its final distance, while the outer invariant remains true for all earlier vertices.

For correctness, every path to a vertex $v$ ends with an edge $uv$ from an earlier vertex in the topological ordering. When $v$ is reached, all those earlier distances are correct and all incoming edges have been relaxed. Thereforewith infinite distance for unreachable vertices and the empty path included at the source. No directed path can return to the source in a Directed acyclic graph. Induction over the topological ordering proves all distances correct. Following predecessor links backward reconstructs each reachable shortest path.

With adjacency lists, topological sorting takes $O(|V|+|E|)$ time and the relaxation pass has the same bound, using $O(|V|)$ extra space beyond the input. Thus the full distance and predecessor representation costs $O(|V|+|E|)$ time. Printing every source-to-vertex path separately can take more time because their total output length may be quadratic. The stipulated nonnegative costs are sufficient; this algorithm actually also permits negative costs because there are no directed graph cycles.