Greedy Technique
Contents
Introduction
What is greedy technique?
-
Domain.
This technique works on optimization problems. -
Core idea.
Choose the best option in every step. -
Assumption.
Local optimality at every step leads to global optimality.
(This idea is not true in general but works for a few important problems.)
Coin Change $\rightarrow$ Cashier's Algorithm
Problem
$\sum_{i=1}^{k} C[i]\cdot D[i] = n$ and $\sum_{i=1}^{k} C[i]$ is minimized.
Cashier's greedy technique
Repeatedly take as many coins as possible of the largest denomination that does not exceed the remaining amount, then move to the next smaller denomination.
Example
A cashier has an infinite supply of coins of denominations $D = 100, 10, 5, 1$. Devise a method to pay any amount $n$ to customer using fewest number of coins.
If coin denominations $= [ 100, 10, 5, 1 ]$, $n = 128$, then mincoins $= 7$, because,
Cashier's greedy algorithm
\begin{algorithm}
\begin{algorithmic}
\FUNCTION{Cashier'sGreedyAlgorithm}{$n, D[1 \ldots k]$}
\STATE \textbf{Input:} Value $n$; array $D[1 \ldots k]$ of distinct positive coin denominations
\STATE \textbf{Output:} Array $C[1 \ldots k]$ and $mincoins$, where $C[i]$ is the number of coins of denomination $D[i]$ (after sorting $D$), or a report that no solution was found
\IF{$n < 0$}
\RETURN \textbf{``Invalid input: $n$ must be non-negative"}
\ENDIF
\STATE Sort $D[1 \ldots k]$ in decreasing order
\STATE $C[1 \ldots k] \gets [0, 0, \ldots, 0]$
\STATE $mincoins \gets 0$
\STATE $remaining \gets n$
\FOR{$i \gets 1$ \TO $k$}
\IF{$remaining = 0$}
\STATE \textbf{break}
\ENDIF
\IF{$D[i] \le remaining$}
\STATE $C[i] \gets \lfloor remaining / D[i] \rfloor$
\STATE $remaining \gets remaining - C[i] \cdot D[i]$ \COMMENT{greedy choice}
\STATE $mincoins \gets mincoins + C[i]$
\ENDIF
\ENDFOR
\IF{$remaining > 0$}
\RETURN \textbf{``No solution found: $remaining$ cannot be paid using $D$"}
\ENDIF
\RETURN $C[1 \ldots k]$ and $mincoins$
\ENDFUNCTION
\end{algorithmic}
\end{algorithm}
Cases handled:
- $n < 0$ is invalid input.
- $n = 0$ needs 0 coins (all $C[i]=0$).
- $k = 0$ with $n > 0$ gives no solution.
- If a nonzero remainder is left after all denominations are used, the greedy algorithm reports failure. This happens, for example, when $1 \notin D$.
Non-optimality of cashier's greedy algorithm
| Denominations | Optimal? | Counterexample |
|---|---|---|
| $[100, 10, 5, 1]$ | ✓ | $-$ |
| $[ (k_1..k_m), \ldots, (k_1 k_2), k_1, 1 ]$ | ✓ | $-$ |
| $[ 4, 3, 1 ]$ | ✗ | Cashier: $6 = 4 + 1 + 1$ Optimal: $6 = 3 + 3$ |
| $[ 5, 3, 2 ]$ | Infeasible | Cashier: $6 = 5 + ?$ Optimal: $6 = 3 + 3$ |
Single-Source All-Target Shortest Path $\rightarrow$ Dijkstra's Algorithm
Output: For every $v\in V$, the shortest-path distance and actual shortest path from source $s$ to vertex $v$.
Dijkstra's Greedy Technique
Create a shortest path tree starting from source $s$ and adding a nearest vertex to the tree and expanding the tree.Dijkstra's Algorithm: Version 1
\begin{algorithm}
\begin{algorithmic}
\FUNCTION{Dijkstra-Version1}{$G, s$}
\STATE \textbf{Input:} Weighted digraph $G$ with nonnegative weights and source vertex $s$
\STATE \textbf{Output:} Shortest path and its cost for every vertex $v$ in $V$
\STATE \{ Initial shortest path tree \}
\STATE $T \gets s$
\STATE \{ Evolving shortest path tree adding $|V|-1$ vertices to it \}
\FOR{$i \gets 1$ \TO $(|V| - 1)$}
\STATE add to $T$ the $i$th nearest vertex to source $s$ \COMMENT{greedy choice}
\ENDFOR
\RETURN $T$
\ENDFUNCTION
\end{algorithmic}
\end{algorithm}
Example
| Step | Removed vertex | Vertex A | Vertex B | Vertex C | Vertex D | Vertex E |
|---|---|---|---|---|---|---|
| 0 | - | (∞, -) | (∞, -) | (∞, -) | (∞, -) | (∞, -) |
| 1 | A | (0, -) | (3, A) | (∞, -) | (7, A) | (∞, -) |
| 2 | B | (0, -) | (3, A) | (7, B) | (5, B) | (∞, -) |
| 3 | D | (0, -) | (3, A) | (7, B) | (5, B) | (9, D) |
| 4 | C | (0, -) | (3, A) | (7, B) | (5, B) | (9, D) |
| 5 | E | (0, -) | (3, A) | (7, B) | (5, B) | (9, D) |
Dijkstra's Algorithm: Version 2
Question: How do we know which vertex is the next nearest?
Answer: We keep a number $distance[v]$ for each vertex, an upper bound on its true distance. The next nearest vertex is the one outside $T$ with the smallest estimate. After adding $u$ to $T$, we check whether $u$ offers its neighbors a shorter route.
\begin{algorithm}
\begin{algorithmic}
\FUNCTION{Dijkstra-Version2}{$G, s$}
\STATE \textbf{Input:} Weighted digraph $G$ with nonnegative weights and source vertex $s$
\STATE \textbf{Output:} Shortest distance $distance[v]$ for every vertex $v$ in $V$
\STATE \{ Initially, only the source is known to be reachable \}
\FOR{each vertex $v \in V$}
\STATE $distance[v] \gets \infty$
\ENDFOR
\STATE $distance[s] \gets 0$
\STATE $T \gets \emptyset$
\STATE \{ Evolving shortest path tree adding $|V|$ vertices to it \}
\FOR{$i \gets 1$ \TO $|V|$}
\STATE $u \gets$ vertex not in $T$ with the smallest $distance[u]$ \COMMENT{greedy choice}
\STATE $T \gets T \cup \{u\}$
\STATE \{ Check whether going through $u$ shortens the route to a neighbor \}
\FOR{each neighbor $v$ of $u$}
\STATE $distance[v] \gets \min(distance[v],\ distance[u] + w(u,v))$
\ENDFOR
\ENDFOR
\RETURN $distance$
\ENDFUNCTION
\end{algorithmic}
\end{algorithm}
Dijkstra's Algorithm: Version 3
Question: How do we know which path improves the path?
Answer: We keep a variable $parent[v]$ for each vertex, to denote the predecessor or parent which improves the shortest path from $s$ to that vertex $v$.
\begin{algorithm}
\begin{algorithmic}
\FUNCTION{Dijkstra-Version3}{$G, s$}
\STATE \textbf{Input:} Weighted digraph $G$ with nonnegative weights and source vertex $s$
\STATE \textbf{Output:} $distance[v]$ and $parent[v]$ for every vertex $v$ in $V$
\STATE \{ Initialization \}
\FOR{each vertex $v \in V$}
\STATE $distance[v] \gets \infty$
\STATE $parent[v] \gets null$
\ENDFOR
\STATE $distance[s] \gets 0$
\STATE $T \gets \emptyset$
\STATE \{ Evolving shortest path tree adding $|V|$ vertices to it \}
\FOR{$i \gets 1$ \TO $|V|$}
\STATE $u \gets$ vertex not in $T$ with the smallest $distance[u]$
\STATE $T \gets T \cup \{u\}$
\STATE \{ Consider every edge leaving $u$ \}
\FOR{each neighbor $v$ of $u$}
\IF{$distance[u] + w(u,v) < distance[v]$}
\STATE $distance[v] \gets distance[u] + w(u,v)$
\STATE $parent[v] \gets u$
\ENDIF
\ENDFOR
\ENDFOR
\RETURN $distance, parent$
\ENDFUNCTION
\end{algorithmic}
\end{algorithm}
The edges $(parent[v], v)$ form the shortest path tree $T$ promised in Version 1. This version is already a correct algorithm, running in $O(|V|^2)$ because each “find the smallest” step scans all vertices.
Dijkstra's Algorithm: Version 4
Question: The line “vertex not in $T$ with the smallest distance” is the bottleneck. How can we efficiently execute this line?
Answer: We can use a min-priority queue $Q$ for representing the set of all vertices not in $T$, keyed by $distance$. Removing a vertex from $Q$ is adding it to $T$, so $T$ is no longer needed explicitly.
\begin{algorithm}
\begin{algorithmic}
\FUNCTION{Dijkstra-Version4}{$G, s$}
\STATE \textbf{Input:} Weighted digraph $G$ with nonnegative weights and source vertex $s$
\STATE \textbf{Output:} $distance[v]$ and $parent[v]$ for every vertex $v$ in $V$
\STATE \{ Initialization \}
\FOR{each vertex $v \in V$}
\STATE $distance[v] \gets \infty$
\STATE $parent[v] \gets null$
\ENDFOR
\STATE $distance[s] \gets 0$
\STATE \{ Queue holds (vertex, key) pairs; Consisting of Unsettled vertices, keyed by their current distance \}
\STATE $Q \gets$ new MinPriorityQueue
\FOR{each vertex $v \in V$}
\STATE $Q.\text{Insert}(v,\ distance[v])$
\ENDFOR
\WHILE{\NOT $Q.\text{IsEmpty}()$}
\STATE $(u, key) \gets Q.\text{RemoveMin}()$ \COMMENT{$u$ joins the tree; $distance[u]$ is final}
\FOR{each neighbor $v$ of $u$}
\IF{$distance[u] + w(u,v) < distance[v]$}
\STATE $distance[v] \gets distance[u] + w(u,v)$
\STATE $parent[v] \gets u$
\STATE $Q.\text{DecreaseKey}(v,\ distance[v])$
\ENDIF
\ENDFOR
\ENDWHILE
\RETURN $distance, parent$
\ENDFUNCTION
\end{algorithmic}
\end{algorithm}
With a binary heap, the total time is $O((|V|+|E|)\log |V|)$. Each vertex is removed once, and each edge triggers at most one DecreaseKey. If $v$ has already been removed, the "if" can never succeed because weights are nonnegative, so DecreaseKey is never called on a settled vertex.
Dijkstra's Algorithm: Version 5
Question: Many standard libraries (for example, Java’s PriorityQueue or C++’s priority_queue or Python's heapq) have no DecreaseKey. What should we do then?
Answer: Instead of changing a key, we insert a new entry and ignore outdated ones when they surface.
\begin{algorithm}
\begin{algorithmic}
\FUNCTION{Dijkstra-Version5}{$G, s$}
\STATE \textbf{Input:} Weighted digraph $G$ with nonnegative weights and source vertex $s$
\STATE \textbf{Output:} $distance[v]$ and $parent[v]$ for every vertex $v$ in $V$
\STATE \{ Initialization \}
\FOR{each vertex $v \in V$}
\STATE $distance[v] \gets \infty$
\STATE $parent[v] \gets null$
\ENDFOR
\STATE $distance[s] \gets 0$
\STATE \{ Queue holds (vertex, key) pairs; it may contain several entries per vertex \}
\STATE $Q \gets$ new MinPriorityQueue
\STATE $Q.\text{Insert}(s,\ 0)$
\WHILE{\NOT $Q.\text{IsEmpty}()$}
\STATE $(u, key) \gets Q.\text{RemoveMin}()$
\IF{$key = distance[u]$} \COMMENT{otherwise a stale entry: skip it}
\FOR{each neighbor $v$ of $u$}
\IF{$distance[u] + w(u,v) < distance[v]$}
\STATE $distance[v] \gets distance[u] + w(u,v)$
\STATE $parent[v] \gets u$
\STATE $Q.\text{Insert}(v,\ distance[v])$
\ENDIF
\ENDFOR
\ENDIF
\ENDWHILE
\RETURN $distance, parent$
\ENDFUNCTION
\end{algorithmic}
\end{algorithm}
The queue now holds at most $|E|$ entries, so the time is $O(|E|\log |E|) = O(|E|\log |V|)$, the same bound as Version 4 for practical purposes. The queue starts with only the source, since the other vertices are discovered through relaxation. A vertex with a stale entry has already been processed through a better, earlier entry.
Why does Version 5 work?
The "if $key = distance[u]$" test works because of one fact: the keys stored for a vertex only ever decrease, and distance[u] is always equal to the smallest key ever inserted for $u$.
Three cases:
- Case $key > distance[u]$: This case is impossible, because $distance[u]$ never increases, and the key was a past value of $distance[u]$.
- Case $key < distance[u]$: A better route was found after this entry was inserted.
- Case $key = distance[u]$: This is the best route found so far to $u$.
The "if $key = distance[u]$" condition is for efficiency and not correctness.
- Case with condition: Total time is $O(|E|\log|V|)$.
- Case without condition: Algorithm is still correct but slow. Too many unwanted entries processed, so total time is $O(|V| \cdot |E|)$.
Dijkstra's Algorithm: Version 6
When we need only the route to one target $t$, can we do better?
When we need only the route to one target $t$, we can stop as soon as $t$ is removed from the queue.
\begin{algorithm}
\begin{algorithmic}
\FUNCTION{Dijkstra-Version6}{$G, s, t$}
\STATE \textbf{Input:} Weighted digraph $G$ with nonnegative weights, source $s$, target $t$
\STATE \textbf{Output:} $distance[v]$ and $parent[v]$ (final for $t$ and all vertices nearer than $t$)
\FOR{each vertex $v \in V$}
\STATE $distance[v] \gets \infty$
\STATE $parent[v] \gets null$
\ENDFOR
\STATE $distance[s] \gets 0$
\STATE $Q \gets$ new MinPriorityQueue
\STATE $Q.\text{Insert}(s,\ 0)$
\WHILE{\NOT $Q.\text{IsEmpty}()$}
\STATE $(u, key) \gets Q.\text{RemoveMin}()$
\IF{$key = distance[u]$}
\IF{$u = t$}
\RETURN $distance, parent$ \COMMENT{$distance[t]$ is final: stop early}
\ENDIF
\FOR{each neighbor $v$ of $u$}
\IF{$distance[u] + w(u,v) < distance[v]$}
\STATE $distance[v] \gets distance[u] + w(u,v)$
\STATE $parent[v] \gets u$
\STATE $Q.\text{Insert}(v,\ distance[v])$
\ENDIF
\ENDFOR
\ENDIF
\ENDWHILE
\RETURN $distance, parent$ \COMMENT{$t$ is unreachable}
\ENDFUNCTION
\end{algorithmic}
\end{algorithm}
\begin{algorithm}
\begin{algorithmic}
\FUNCTION{ShortestPath}{$parent, distance, s, t$}
\STATE \textbf{Input:} Output of Dijkstra-Version5 and the endpoints $s$, $t$
\STATE \textbf{Output:} List of vertices on a shortest path from $s$ to $t$, or an empty list
\IF{$distance[t] = \infty$}
\RETURN empty list \COMMENT{no path exists}
\ENDIF
\STATE $path \gets$ new List
\STATE $x \gets t$
\WHILE{$x \neq null$}
\STATE $path.\text{AddFirst}(x)$
\STATE $x \gets parent[x]$
\ENDWHILE
\RETURN $path$
\ENDFUNCTION
\end{algorithmic}
\end{algorithm}
Early stopping is safe because the first time a vertex leaves the queue, its distance is final. Path retrieval takes $O(\text{path length})$ time.
| Version | Core question answered | Time |
|---|---|---|
| 1 | What is the greedy strategy? | NA (idea only) |
| 2 | How is "nearest" defined computationally? | $O(|V|^2)$ |
| 3 | How do we get the paths, not just costs? | $O(|V|^2)$ |
| 4 | How do we make the greedy choice fast? | $O((|V| + |E|) \log |V|)$ |
| 5 | What if the library has no DecreaseKey? | $O(|E| \log |V|)$ |
| 6 | How do we stop early and print the route when there is only one target? | $O(|E| \log |V|)$, often much faster in practice |
More Examples
Source: CLRS' Introduction to Algorithms textbook
Source: Jeff Erickson's Algorithms book. (https://jeffe.cs.illinois.edu/teaching/algorithms/)
Minimum Spanning Tree $\rightarrow$ Jarnik's Algorithm
Output: A subset of edges $T \subseteq E$ such that
- $T$ is spanning: i.e., $T$ connects all vertices of $V$,
- $T$ is a tree: i.e., $T$ contains no cycle (so $|T| = |V| - 1$), and
- $T$ has the smallest weight: i.e, the total weight $w(T) = \sum_{(u, v) \in T} w(u, v)$ is as small as possible.
Example
Consider this graph.
Source: (https://commons.wikimedia.org/wiki/Category:Complete_graph_K4#/media/File:Complete_graph_K4.svg)
List of all spanning trees of the given graph are:
Source: (https://de.wikipedia.org/wiki/Datei:Spanning_Trees_qtl1.svg)
Jarnik's Algorithm: Version 1
\begin{algorithm}
\begin{algorithmic}
\FUNCTION{Jarnik-Version1}{$G, s$}
\STATE \textbf{Input:} Connected weighted undirected graph $G$ and a start vertex $s$
\STATE \textbf{Output:} Edge set $F$ of a minimum spanning tree of $G$
\STATE \{ Initial tree contains only the start vertex \}
\STATE $T \gets \{s\}$
\STATE $F \gets \emptyset$
\STATE \{ Evolving tree adding $|V|-1$ vertices and edges to it \}
\FOR{$i \gets 1$ \TO $(|V| - 1)$}
\STATE find the lightest edge $(u, v)$ with $u \in T$ and $v \notin T$
\STATE add $v$ to $T$ and add edge $(u, v)$ to $F$
\ENDFOR
\RETURN $F$
\ENDFUNCTION
\end{algorithmic}
\end{algorithm}
Example
| Step | Removed vertex | Vertex A | Vertex B | Vertex C | Vertex D | Vertex E |
|---|---|---|---|---|---|---|
| 0 | - | (∞, -) | (∞, -) | (∞, -) | (∞, -) | (∞, -) |
| 1 | A | (0, -) | (3, A) | (∞, -) | (7, A) | (∞, -) |
| 2 | B | (0, -) | (3, A) | (4, B) | (2, B) | (∞, -) |
| 3 | D | (0, -) | (3, A) | (4, B) | (2, B) | (4, D) |
| 4 | C | (0, -) | (3, A) | (4, B) | (2, B) | (4, D) |
| 5 | E | (0, -) | (3, A) | (4, B) | (2, B) | (4, D) |
Jarnik's Algorithm: Version 2
Question: How do we know which vertex is the next nearest to the tree?
Answer: We keep a number $distance[v]$ for each vertex, the weight of the lightest edge found so far that connects $v$ to the tree. The next vertex to add is the one outside $T$ with the smallest estimate. After adding $u$ to $T$, we check whether $u$ offers each neighbor outside $T$ a cheaper connection. Unlike Dijkstra's algorithm, we compare only the single edge weight $w(u,v)$, not a total along a path.
\begin{algorithm}
\begin{algorithmic}
\FUNCTION{Jarnik-Version2}{$G, s$}
\STATE \textbf{Input:} Connected weighted undirected graph $G$ and a start vertex $s$
\STATE \textbf{Output:} $distance[v]$ for every vertex $v$, the weight of the tree edge that connects $v$
\STATE \{ Initially, no vertex is connected to the tree \}
\FOR{each vertex $v \in V$}
\STATE $distance[v] \gets \infty$
\ENDFOR
\STATE $distance[s] \gets 0$
\STATE $T \gets \emptyset$
\STATE \{ Evolving tree adding $|V|$ vertices to it \}
\FOR{$i \gets 1$ \TO $|V|$}
\STATE $u \gets$ vertex not in $T$ with the smallest $distance[u]$ \COMMENT{greedy choice}
\STATE $T \gets T \cup \{u\}$
\STATE \{ Check whether $u$ offers a cheaper connection to a neighbor \}
\FOR{each neighbor $v$ of $u$ with $v \notin T$}
\STATE $distance[v] \gets \min(distance[v],\ w(u,v))$
\ENDFOR
\ENDFOR
\RETURN $distance$
\ENDFUNCTION
\end{algorithmic}
\end{algorithm}
Jarník's Algorithm: Version 3
Question: Version 2 gives only the weights of the tree edges. How do we know which edges form the tree?
Answer: We keep a variable $parent[v]$ for each vertex, to denote the tree vertex whose edge gave $v$ its current cheapest connection. When the update test $w(u,v) < distance[v]$ succeeds, we set $parent[v] \gets u$. At the end, the edges $(parent[v], v)$ for all $v \neq s$ form the minimum spanning tree. We must also test $v \notin T$ before updating: a vertex already in the tree must keep its $distance$ and $parent$, otherwise the tree would be corrupted.
\begin{algorithm}
\begin{algorithmic}
\FUNCTION{Jarnik-Version3}{$G, s$}
\STATE \textbf{Input:} Connected weighted undirected graph $G$ and a start vertex $s$
\STATE \textbf{Output:} $distance[v]$ and $parent[v]$ for every vertex $v$ in $V$
\STATE \{ Initialization \}
\FOR{each vertex $v \in V$}
\STATE $distance[v] \gets \infty$
\STATE $parent[v] \gets null$
\ENDFOR
\STATE $distance[s] \gets 0$
\STATE $T \gets \emptyset$
\STATE \{ Evolving tree adding $|V|$ vertices to it \}
\FOR{$i \gets 1$ \TO $|V|$}
\STATE $u \gets$ vertex not in $T$ with the smallest $distance[u]$
\STATE $T \gets T \cup \{u\}$
\STATE \{ Update every neighbor of $u$ that is still outside the tree \}
\FOR{each neighbor $v$ of $u$}
\IF{$v \notin T$ \AND $w(u,v) < distance[v]$}
\STATE $distance[v] \gets w(u,v)$
\STATE $parent[v] \gets u$
\ENDIF
\ENDFOR
\ENDFOR
\RETURN $distance, parent$
\ENDFUNCTION
\end{algorithmic}
\end{algorithm}
Jarník's Algorithm: Version 4
Question: The line “vertex not in $T$ with the smallest distance” is the bottleneck. How can we efficiently execute this line?
Answer: We can use a min-priority queue $Q$ for representing the set of all vertices not in $T$, keyed by $distance$. Removing a vertex from $Q$ is adding it to $T$, so $T$ is no longer needed explicitly, and the test $v \notin T$ becomes $Q.\text{Contains}(v)$. When a neighbor's $distance$ improves, we call $Q.\text{DecreaseKey}$ to move it forward in the queue.
\begin{algorithm}
\begin{algorithmic}
\FUNCTION{Jarnik-Version4}{$G, s$}
\STATE \textbf{Input:} Connected weighted undirected graph $G$ and a start vertex $s$
\STATE \textbf{Output:} $distance[v]$ and $parent[v]$ for every vertex $v$ in $V$
\STATE \{ Initialization \}
\FOR{each vertex $v \in V$}
\STATE $distance[v] \gets \infty$
\STATE $parent[v] \gets null$
\ENDFOR
\STATE $distance[s] \gets 0$
\STATE \{ Vertices not yet in the tree, keyed by their current connection cost \}
\STATE $Q \gets$ new MinPriorityQueue
\FOR{each vertex $v \in V$}
\STATE $Q.\text{Insert}(v,\ distance[v])$
\ENDFOR
\WHILE{\NOT $Q.\text{IsEmpty}()$}
\STATE $u \gets Q.\text{RemoveMin}()$ \COMMENT{$u$ joins the tree through edge $(parent[u], u)$}
\FOR{each neighbor $v$ of $u$}
\IF{$Q.\text{Contains}(v)$ \AND $w(u,v) < distance[v]$}
\STATE $distance[v] \gets w(u,v)$
\STATE $parent[v] \gets u$
\STATE $Q.\text{DecreaseKey}(v,\ distance[v])$
\ENDIF
\ENDFOR
\ENDWHILE
\RETURN $distance, parent$
\ENDFUNCTION
\end{algorithmic}
\end{algorithm}
Jarník's Algorithm: Version 5
Question: Many standard libraries (for example, Java's PriorityQueue or C++'s priority_queue or Python's heapq) have no DecreaseKey. What should we do then?
Answer: Instead of changing a key, we insert a new entry with the smaller $distance$ and ignore outdated ones when they surface. Since a vertex can now appear in the queue several times, we keep a flag $intree[v]$. The first time a vertex is removed, it comes out with its best $distance$ and is marked as in the tree. Any later entry for it is outdated and is skipped.
\begin{algorithm}
\begin{algorithmic}
\FUNCTION{Jarnik-Version5}{$G, s$}
\STATE \textbf{Input:} Connected weighted undirected graph $G$ and a start vertex $s$
\STATE \textbf{Output:} $distance[v]$ and $parent[v]$ for every vertex $v$ in $V$
\STATE \{ Initialization \}
\FOR{each vertex $v \in V$}
\STATE $distance[v] \gets \infty$
\STATE $parent[v] \gets null$
\STATE $intree[v] \gets false$
\ENDFOR
\STATE $distance[s] \gets 0$
\STATE \{ Queue holds (vertex, distance) pairs; it may contain several entries per vertex \}
\STATE $Q \gets$ new MinPriorityQueue
\STATE $Q.\text{Insert}(s,\ 0)$
\WHILE{\NOT $Q.\text{IsEmpty}()$}
\STATE $(u, k) \gets Q.\text{RemoveMin}()$
\IF{\NOT $intree[u]$} \COMMENT{otherwise a stale entry: skip it}
\STATE $intree[u] \gets true$
\FOR{each neighbor $v$ of $u$}
\IF{\NOT $intree[v]$ \AND $w(u,v) < distance[v]$}
\STATE $distance[v] \gets w(u,v)$
\STATE $parent[v] \gets u$
\STATE $Q.\text{Insert}(v,\ distance[v])$
\ENDIF
\ENDFOR
\ENDIF
\ENDWHILE
\RETURN $distance, parent$
\ENDFUNCTION
\end{algorithmic}
\end{algorithm}
Jarník's Algorithm: Version 6
Question: Once every vertex is in the tree, the queue may still contain outdated entries. How do we avoid wasting time on them, and how do we report the result?
Answer: We count the vertices added to the tree and stop as soon as the count reaches $|V|$, because every remaining entry must be outdated. We also add $distance[u]$ to $totalweight$ each time a vertex joins the tree, which gives the weight of the minimum spanning tree. Finally, a separate function collects the edges $(parent[v], v)$ with their weights $distance[v]$ into a list.
\begin{algorithm}
\begin{algorithmic}
\FUNCTION{Jarnik-Version6}{$G, s$}
\STATE \textbf{Input:} Connected weighted undirected graph $G$ and a start vertex $s$
\STATE \textbf{Output:} $distance[v]$, $parent[v]$ for every vertex $v$ in $V$, and $totalweight$ of the tree
\FOR{each vertex $v \in V$}
\STATE $distance[v] \gets \infty$
\STATE $parent[v] \gets null$
\STATE $intree[v] \gets false$
\ENDFOR
\STATE $distance[s] \gets 0$
\STATE $totalweight \gets 0$
\STATE $count \gets 0$
\STATE $Q \gets$ new MinPriorityQueue
\STATE $Q.\text{Insert}(s,\ 0)$
\WHILE{\NOT $Q.\text{IsEmpty}()$}
\STATE $(u, k) \gets Q.\text{RemoveMin}()$
\IF{\NOT $intree[u]$}
\STATE $intree[u] \gets true$
\STATE $totalweight \gets totalweight + distance[u]$
\STATE $count \gets count + 1$
\IF{$count = |V|$}
\RETURN $distance, parent, totalweight$ \COMMENT{all vertices are in the tree: stop early}
\ENDIF
\FOR{each neighbor $v$ of $u$}
\IF{\NOT $intree[v]$ \AND $w(u,v) < distance[v]$}
\STATE $distance[v] \gets w(u,v)$
\STATE $parent[v] \gets u$
\STATE $Q.\text{Insert}(v,\ distance[v])$
\ENDIF
\ENDFOR
\ENDIF
\ENDWHILE
\RETURN $distance, parent, totalweight$ \COMMENT{$G$ is disconnected: tree spans only the component of $s$}
\ENDFUNCTION
\end{algorithmic}
\end{algorithm}
| Version | Core question answered | Time |
|---|---|---|
| 1 | What is the greedy strategy? | NA (idea only) |
| 2 | How is "nearest to the tree" defined computationally? | $O(|V|^2)$ |
| 3 | How do we get the tree edges, not just their weights? | $O(|V|^2)$ |
| 4 | How do we make the greedy choice fast? | $O((|V| + |E|) \log |V|)$ |
| 5 | What if the library has no DecreaseKey? | $O(|E| \log |V|)$ |
| 6 | How do we stop early and report the tree and its total weight? | $O(|E| \log |V|)$, with a cleaner interface |
More Examples
Source: Jeff Erickson's Algorithms book. (https://jeffe.cs.illinois.edu/teaching/algorithms/)
Source: (http://users.cecs.anu.edu.au/~Alistair.Rendell)
Source: CLRS' Introduction to Algorithms textbook
Minimum Spanning Tree $\rightarrow$ Kruskal's Algorithm
Kruskal's Algorithm: Version 1
\begin{algorithm}
\begin{algorithmic}
\FUNCTION{Kruskal-Version1}{$G$}
\STATE \textbf{Input:} Graph $G$
\STATE \textbf{Output:} Minimum spanning tree $T$ of $G$
\STATE forest $T \gets \phi$
\FOR{$(|V| - 1)$ times}
\STATE add to forest $T$ a shortest edge that does not introduce a cycle in $T$
\ENDFOR
\RETURN $T$
\ENDFUNCTION
\end{algorithmic}
\end{algorithm}
Example 1
Source: Jeff Erickson's Algorithms book. (https://jeffe.cs.illinois.edu/teaching/algorithms/)
Example 2
Source: Anany Levitin's Introduction to Design and Analysis of Algorithms textbook
Example 3
Source: (http://users.cecs.anu.edu.au/~Alistair.Rendell)
Example 4
Source: CLRS' Introduction to Algorithms textbook
Example 5
Source: CLRS' Introduction to Algorithms textbook
Kruskal's Algorithm: Version 2
\begin{algorithm}
\begin{algorithmic}
\FUNCTION{Kruskal-Version2}{$G, weight$}
\STATE \textbf{Input:} Graph $G$
\STATE \textbf{Output:} Set of edges $E_T$ composing a minimum spanning tree $T$ of $G$
\STATE sort $E$ in nondecreasing order of the edge weights
\STATE suppose $weight(e_{1}) \le weight(e_{2}) \le \cdots \le weight(e_{{|E|}})$
\STATE forest $T$ is defined by its edges $E_T$
\STATE $E_T \gets \phi$; $ecount \gets 0$ \COMMENT{initialize the set of forest edges and its size}
\STATE $k \gets 0$ \COMMENT{initialize the number of processed edges}
\WHILE{$edgecount < |V| - 1$}
\STATE $k \gets k+1$
\IF{$E_T \cup \{e_{k}\}$ is acyclic}
\STATE $E_T \gets E_T \cup \{e_{k}\}$
\STATE $edgecount \gets edgecount + 1$
\ENDIF
\ENDWHILE
\RETURN $E_T$
\ENDFUNCTION
\end{algorithmic}
\end{algorithm}
Union-find ADT
Kruskal's algorithm requires dynamic partitioning of $n$-element set
$S$ into a collection of disjoint subsets $S_1, S_2, \ldots, S_k$.
What is a good ADT for solving this problem?
Union-find ADT
What are the operations in a union-find ADT?
| Method | Functionality |
|---|---|
| MakeSet(x) | Creates one-element set $\{x\}$. |
| FindSet(x) | Returns a subset containing $x$. |
| UnionSet(x,y) | Constructs the union of subsets $S_x$ and $S_y$ containing $x$ and $y$, respectively, and adds it to the collection to replace $S_x$ and $S_y$, which are deleted from it. |
Let set $S = \{ 1, 2, 3, 4, 5, 6 \}$
| Method | Return value | Union-find contents |
|---|---|---|
| MakeSet(1) | - | $\{ 1 \}$ |
| MakeSet(2) | - | $\{ 1 \}, \{ 2 \}$ |
| $\cdots$ | $\cdots$ | $\cdots$ |
| MakeSet(6) | - | $\{1\}, \{2\}, \{3\}, \{4\}, \{5\}, \{6\}$ |
| FindSet(3) | $\{3\}$ | $\{1\}, \{2\}, \{3\}, \{4\}, \{5\}, \{6\}$ |
| UnionSet(1,4) | - | $\{1,4\}, \{2\}, \{3\}, \{5\}, \{6\}$ |
| UnionSet(5,2) | - | $\{1,4\}, \{5, 2\}, \{3\}, \{6\}$ |
| UnionSet(4,5) | - | $\{1,4,5,2\}, \{3\}, \{6\}$ |
| FindSet(2) | $\{1,4,5,2\}$ | $\{1,4,5,2\}, \{3\}, \{6\}$ |
| UnionSet(3,6) | - | $\{1,4,5,2\}, \{3,6\}$ |
| FindSet(6) | $\{3,6\}$ | $\{1,4,5,2\}, \{3,6\}$ |
| UnionSet(6,2) | - | $\{1,4,5,2,3,6\}$ |
Kruskal's Algorithm: Version 3
\begin{algorithm}
\begin{algorithmic}
\FUNCTION{Kruskal-Version3}{$G, weight$}
\STATE \textbf{Input:} Graph $G=(V, E)$
\STATE \textbf{Output:} Minimum spanning tree $T$ of $G$
\STATE forest $T \gets \phi$
\FOR{each vertex $v \in V$}
\STATE \textsc{MakeSet}$(v)$
\ENDFOR
\STATE sort the edges $E$ in nondecreasing order of the edge weights
\STATE suppose $weight(e_{1}) \le weight(e_{2}) \le \cdots \le weight(e_{{|E|}})$
\FOR{each edge $(u, v) \in E$ taken in nondecreasing order by weight}
\IF{\textsc{FindSet}$(u) \ne$ \textsc{FindSet}$(v)$} \COMMENT{$T \cup \{(u, v)\}$ is acyclic}
\STATE $T \gets T \cup \{ (u, v) \}$
\STATE \textsc{UnionSet}$(u, v)$
\ENDIF
\ENDFOR
\RETURN $T$
\ENDFUNCTION
\end{algorithmic}
\end{algorithm}
- Without union-find: Time is $O(|V| \cdot |E|)$
- With union-find: Time is $O(|E| \log |V|)$