Unit 6: Shortest Paths & Trees

Graph theory turns networks of relationships — roads, circuits, dependencies — into vertices joined by edges, so that connectivity and cost become computable. This unit assumes a graph G = (V, E) where V is a set of vertices and E a set of edges, and builds two structures on it: shortest paths (cheapest routes across a weighted graph) and trees (connected, acyclic skeletons).

Recurring conventions used throughout:

• Graph: a pair G = (V, E); |V| = n vertices, |E| = m edges.
• Adjacency: two vertices are adjacent if joined by an edge; an edge is incident to its endpoints.
• Path: a sequence of distinct vertices each adjacent to the next; its length is the number of edges (unweighted) or the sum of edge weights (weighted).
• Cycle: a path that returns to its start; acyclic means no cycle exists.
• Connected: every pair of vertices is joined by some path.
• Directed vs undirected: edges either have an orientation (arcs) or none.

II. Labelled and Weighted Graphs

Attaching data to a bare graph

A labelled graph carries information on its vertices or edges; a weighted graph is the special case where each edge carries a number.

A. Labelled graph

A labelled graph assigns identifiers or attributes to vertices and/or edges.

• Definition: a graph together with a labelling function, e.g. l: V → L mapping each vertex to a label from set L.
• Purpose: distinguishes otherwise identical structural positions — city names on map nodes, pin numbers on circuit terminals.
• Vertex vs edge labels: vertex labels name the objects; edge labels name the relationship (e.g. "highway", "friendship").

B. Weighted graph

A weighted graph is a labelled graph whose edge labels are numeric costs.

• Definition: G = (V, E, w) with a weight function w: E → ℝ, so each edge (u, v) has weight w(u, v).
• Interpretation: weights model distance, time, capacity or price; a road network uses kilometres.
• Storage: a weight (adjacency) matrix W where W[i][j] = w(i, j) if the edge exists, ∞ if absent, 0 on the diagonal.
• Path weight: for a path v₀, v₁, …, vₖ, total weight = Σ w(vᵢ, vᵢ₊₁).

III. Shortest Paths in Weighted Graphs

Finding the cheapest route between vertices

The shortest-path problem asks for a path of minimum total weight between two vertices, not merely the fewest edges.

A. Shortest path in weighted graphs

The shortest path from s to t minimises summed edge weight over all s–t paths.

• Distance: δ(s, t) denotes the minimum total weight; if no path exists, δ(s, t) = ∞.
• Optimal substructure: any subpath of a shortest path is itself shortest — the property every shortest-path algorithm exploits.
• Single-source: compute δ(s, v) for all v from one source s.
• Non-negative weights required: the standard efficient method assumes w(e) ≥ 0; negative weights break the greedy argument.
• Contrast with unweighted case: in an unweighted graph a breadth-first search suffices because every edge costs 1; weights force a cost-ordered search instead.

B. Dijkstra's algorithm to find shortest path

Dijkstra's algorithm (Edsger Dijkstra, 1959) computes single-source shortest paths in a graph with non-negative edge weights by greedily fixing the closest unvisited vertex.

• Principle: maintain a tentative distance dist[v]; repeatedly pick the unvisited vertex of smallest dist, mark it final, and relax its outgoing edges.
• Relaxation: for edge (u, v), if dist[u] + w(u, v) < dist[v] then dist[v] ← dist[u] + w(u, v).
• Data structures: a min-priority queue keyed on dist; a prev[] array to reconstruct the path.

Dijkstra(G, s):
    for each v in V: dist[v] ← ∞; prev[v] ← nil
    dist[s] ← 0
    Q ← all vertices (priority queue on dist)
    while Q not empty:
        u ← extract-min(Q)
        for each neighbour v of u:
            if dist[u] + w(u,v) < dist[v]:
                dist[v] ← dist[u] + w(u,v)
                prev[v] ← u

• Symbols: dist[v] = best known distance from s; prev[v] = predecessor of v on the best path; Q = set of not-yet-finalised vertices.
• Complexity: O((n + m) log n) with a binary-heap priority queue; O(n²) with a simple array scan.
• Worked example: vertices A,B,C,D; edges A–B = 1, A–C = 4, B–C = 2, B–D = 5, C–D = 1. Start at A: fix A(0), relax to B(1), C(4); fix B(1), relax C(1+2=3), D(6); fix C(3), relax D(3+1=4); fix D(4). Shortest A→D path is A–B–C–D of weight 4.
• Limitation: fails with negative edges because once a vertex is finalised its distance is never revisited.

IV. Trees

Connected acyclic graphs and their rooted forms

A tree is a minimal connected structure: remove any edge and it disconnects, add any edge and it forms a cycle.

A. Introduction to tree

A tree is a connected undirected graph containing no cycles.

• Definition: connected and acyclic; equivalently, any two vertices are joined by exactly one path.
• Edge count: a tree on n vertices has exactly n − 1 edges — the fewest that keep it connected.
• Leaf and internal: a leaf has degree 1; other vertices are internal.
• Forest: a disjoint collection of trees.
• Equivalent characterisations: connected with n − 1 edges; acyclic with n − 1 edges; a unique path between every vertex pair.

B. Rooted tree

A rooted tree designates one vertex as the root, giving every edge a direction away from it and imposing a parent–child hierarchy.

• Root: the distinguished top vertex, with no parent.
• Parent / child: on the path from the root, the nearer vertex is the parent; siblings share a parent.
• Ancestor / descendant: vertices lying on / below the path from the root.
• Level and height: the root is at level 0; depth of a vertex is its distance from the root; height is the greatest depth.
• Subtree: a vertex together with all its descendants.

C. Binary tree

A binary tree is a rooted tree in which every vertex has at most two children, distinguished as left and right.

• Definition: each node has 0, 1 or 2 children, with ordered left/right positions.
• Full binary tree: every internal node has exactly two children.
• Complete binary tree: all levels filled except possibly the last, which fills left to right.
• Node bound: a binary tree of height h holds at most 2^(h+1) − 1 nodes; level k holds at most 2^k nodes.
• Traversals: preorder (root, left, right), inorder (left, root, right), postorder (left, right, root) — inorder on a binary search tree yields sorted output.

V. Spanning Trees and Minimum Spanning Trees

Skeletons that connect every vertex at least cost

A spanning tree keeps a graph connected using the fewest edges; weighting the graph makes one such tree cheapest.

A. Spanning tree

A spanning tree of a connected graph G is a subgraph that is a tree and includes every vertex of G.

• Definition: a connected acyclic subgraph containing all n vertices and exactly n − 1 edges of G.
• Non-uniqueness: a graph typically has many spanning trees; a complete graph on n vertices has n^(n−2) (Cayley's formula).
• Construction idea: repeatedly remove edges that lie on a cycle until none remain.

B. Minimum spanning tree

A minimum spanning tree (MST) of a weighted connected graph is a spanning tree of least total edge weight.

• Definition: spanning tree T minimising Σ_{e∈T} w(e).
• Cut property: for any partition of vertices, the lightest edge crossing the cut belongs to some MST — the theoretical basis of both algorithms below.
• Uniqueness: if all edge weights are distinct, the MST is unique.

C. Kruskal and Prim's algorithms to find minimum spanning tree

Both build an MST greedily by the cut property, but differ in what they grow.

1. Kruskal's algorithm — edge-based: sort all edges by weight; add each in turn if it joins two so-far-separate components, using a disjoint-set (union–find) structure to detect cycles.

Kruskal(G):
    T ← ∅
    sort E by increasing w
    for each edge (u,v) in sorted order:
        if find(u) ≠ find(v):
            T ← T ∪ {(u,v)}; union(u,v)
    return T

• Complexity: O(m log m), dominated by the sort.
• Best for: sparse graphs, where m is small.

2. Prim's algorithm — vertex-based: start from one vertex and repeatedly attach the cheapest edge that links the growing tree to a vertex outside it, using a priority queue keyed on connection cost.

Prim(G, s):
    add s to tree
    while tree ≠ V:
        pick minimum-weight edge (u,v) with u in tree, v outside
        add v and (u,v) to tree

• Complexity: O(m log n) with a binary heap.
• Best for: dense graphs, where m approaches n².

• Contrast: Kruskal grows a forest of fragments that merge into one tree; Prim grows a single connected tree from a seed. Both yield the same total weight when it is unique.
• Worked example: on the graph A–B = 1, B–C = 2, A–C = 4, C–D = 1, B–D = 5, sorted edges give Kruskal A–B(1), C–D(1), B–C(2) for total weight 4; Prim from A picks A–B(1), B–C(2), C–D(1) for the same tree, with the weight-4 and weight-5 edges rejected as cycle-forming.