Greedy algorithms

Example: Counting money

Suppose you want to count out a certain amount of money, using the fewest possible bills and coins
A greedy algorithm would do this would be:

At each step, take the largest possible bill or coin that does not overshoot

Example: To make $6.39, you can choose:


However, greedy algorithms don't always work.

Consider in some (fictional) monetary system, “krons” come in 1 kron, 7 kron, and 10 kron coins
Using a greedy algorithm to count out 15 krons, you would get


Spaning Trees

Suppose you own a telecom company and you're looking to lay cable in a new neighborhood. ...

A spanning tree T of a connected graph G=(V,E)G = (V,E) is a
subgraph of GG that is:

The minimum spanning tree (MST) problem:
Suppose that we have a connected, undirected graph G=(V,E)G=(V,E), with a numerical weighting w(u,v)w(u,v) for each edge (u,v)(u,v).
Problem: Find an acyclic subset TET \subseteq E that connects all of the vertices in VV, and minimizes:
Σ{w(u,v)(u,v)T}\Sigma \{w(u,v) | (u,v) \in T\}

Solution: We will look for an algorithm of the form:
ETE_T \leftarrow empty set of edges
while (ETE_T is not a spanning tree)
- add an edge to ETE_T
At each stage we will ensure that ETE_T is a subset of a MST


Test yourself

If ee is a minimum-weight edge in a connected
graph, then ee must be an edge in at least one
minimum spanning tree

Must ee be an edge in all minimum
spanning trees of the graph?

If every edge in a connected graph GG has a
distinct weight, then GG must have a unique
minimum spanning tree?

Proof
Assume the contrary, that there are two different MSTs AA and BB.


Prim's Algorithm

Prim's

Idea: Construct a MST by greedily expanding an initial tree, composed of just a single vertex of the graph's vertices. To expand the tree, attach the nearest vertex, i.e. add the vertex connected by the lowest weight edge amongst the neighbors of the current expanding tree such that we don't create a cycle.

Pseudocode:
Input: A weighted connected graph G=(V,E)G = (V,E)
Output: ErE_r the set of edges composing a minimum spanning tree of G.

Prim(G):
Vrv0V_r \leftarrow {v_0}
ErE_r \leftarrow \varnothing
for i1i \leftarrow 1 to V1|V|- 1 do:
    find a minimum-weight edge e=(v,u)e^* = (v^*, u^*) among all the edges (v,u)(v, u) such that vv is in VrV_r and uu is in VVrV - V_r
    VrVr{u}V_r \leftarrow V_r \cup \{u^*\}
    ErEr{e}E_r \leftarrow E_r \cup \{e^*\}
return ErE_r

Let's try two examples


MSTexample.png

MSTexample2.png


A bit more detail:

 1 The input is the graph G=(V, E), and a root r in V.
 2 for each v in V
 3   key[v] ← ∞;
 4   parent[v] ← null;
 5 key[r]0;
 6 add all vertices in V to the queue Q.
 7 while (Q is nonempty):
 8   u ← extractMin(Q);
 9   for each vertex v that is adjacent to u:
10     if v ∈ Q and weight(u,v) < key[v]:
11       parent[v] ← u;
12       key[v] ← weight(u,v);

Ideas: Store all vertices that are not in (VT,ETV_T, E_T) in a priority queue Q with an extractMin operation.
If u is a vertex in Q, what’s key[u] (the value that determines u’s position in Q)?
- key[u] = minimum weight of edge from u into VTV_T
- If no such edge exists, key[u] = ∞.
- We maintain information about the parent (in (VT,ETV_T, E_T)) of each vertex v in an array parent[].
- ETE_T is kept implicitly as {(v, parent[v]) | v ∈ V−Q−{r}}.

Complexity:
The operations that contribute most toward Prim's algorithm revolve around our data structure operations. The input size is measured by V|V| and E|E|.

Assuming a binary heap:


Kruskal's Algorithm

Kruskal's

Idea: create a forest F (a set of trees), where each vertex in the graph is a separate tree
create a set S containing all edges in the graph
while S is not empty ad F is not yet spanning:
-remove and edge with minimum weight from S
-if the removed edge connects to different trees, then add it to F, combining two trees into a single tree
At the termination of the algorithm, the forest forms a minimum spanning tree of the graph.

Pseudocode using the union find data structure:

Kruskal(G):
1  A = null
2  for each v in V:
3    MakeSet(v)
4  for each (u, v) in E, sorted by weight from smallest to largest:
5    if FindSet(u) != FindSet(v):
6      A = A union {(u, v)}
7      Union(u, v)
8  return A

Union Find (disjoint set) data structure
The operations we need are:

Complexity:
The operations that contribute most toward the run time of Kruskal's are:
(1) sorting the edges and (2) the union find operations.

Sorting the edges costs O(ElogE)\mathcal{O}(|E| \log |E|) time.

The union find data structure can perform O(V)\mathcal{O}(|V|) operations in O(VlogV)\mathcal{O}(|V| \log |V|) time.

A sophisticated union find data structure can run in O(α(V))\mathcal{O}(\alpha (|V|)) time.
Combined with a linear time sorting algorithm, we could achieve O(Eα(V))\mathcal{O}(|E| \alpha(|V|)) run time.


Shortest path - Dijkstra’s Algorithm

Dijkstra's

Dijkstra’s finds the lowest cost path from source node and a destination node in a weighted graph. More generally, it finds the shortest path from a source node to every node.

Idea: First, it finds the shortest path from the source to a vertex nearest to it, then to a second nearest, and so on. In general, before its ithi^{th} iteration commences, the algorithm has already identified the shortest paths to i1i − 1 other vertices nearest to the source.

Begin by setting the distance of every node from the source node to infinity and the source node to 0. Then consider the closest unvisited node. (On the first iteration, this will be the source node.) From this node, update the distance to every unvisited neighbor. The update is done by comparing the distance of the node plus the edge to the neighbor to the distance of the neighbor. Update the value if smaller, mark the current node as the parent in the shortest path, and mark the current node as being visited. Repeat until all nodes are visited.

Input: A source node s and destination node d, Graph G =
(V, E) with edge weights {length(u, v) for (u, v) in E}
Output: the path weight from s to d

 1  function Dijkstra(Graph, source):
 2
 3      create vertex set Q
 4
 5      for each vertex v in Graph:             
 6          dist[v] ← INFINITY                  
 7          prev[v] ← UNDEFINED                 
 8          add v to Q                      
10      dist[source]0                        
11      
12      while Q is not empty:
13          u ← vertex in Q with min dist[u]    
14                                              
15          remove u from Q
16          
17          for each neighbor v of u:           
18              alt ← dist[u] + length(u, v)
19              if alt < dist[v]:               
20                  dist[v] ← alt
21                  prev[v] ← u
22
23      return dist[], prev[]

Using a min priority queue, we can get better efficiency. Instead of searching for the min vertex in QQ, QQ could be implemented as a min priority queue and we'd extract the min from QQ and update it - with a decrease-key operation - at each step.

Complexity: (See Dijsktra's on Wikipedia)
Like Prim's and Kruskal's this algorithm's run time primarily depends upon the operations on the data structures. The input size is measured by the number of vertices and edges in the graph.

For any implementation of the vertex set QQ, the running time is in:

O(ETdk+VTem)\mathcal{O}(|E|\cdot T_{dk}+|V|\cdot T_{em})

where TdkT_{dk} and TemT_{em} are the complexities of the decrease-key and extract-minimum operations in QQ, respectively. The simplest implementation of Dijkstra's algorithm stores the vertex set QQ as an ordinary linked list or array, and extract-minimum is simply a linear search through all vertices in QQ. In this case, the running time is O(E+V2)=O(V2)\mathcal{O}(|E|+|V|^{2})= \mathcal{O}(|V|^{2}).

With a self-balancing binary search tree or binary heap, the algorithm improves to:

Θ((E+V)logV)\Theta ((|E|+|V|)\log |V|)

For connected graphs, this can be simplified to Θ(ElogV)\Theta(|E| \log |V|)

In an implementation of Dijkstra's algorithm that supports decrease-key, the priority queue holding the nodes begins with V=n|V| = n nodes in it and on each step of the algorithm removes one node. This means that the total number of heap dequeues is nn. Each node will have decrease-key called on it potentially once for each edge leading into it, so the total number of decrease-keys done is at most mm. This gives a runtime of (nTe+nTd+mTk)(n T_e + n T_d + m T_k), where TkT_k is the time required to call decrease-key.

Queue TeT_e TdT_d TkT_k w/o Dec-Key w/Dec-Key
Array/LL nn O(n2)\mathcal{O}(n^2)
Binary Heap O(logn)\mathcal{O}(\log n) O(logn)\mathcal{O}(\log n) O(logn)\mathcal{O}(\log n) O(mlogn)\mathcal{O}(m \log n) O(mlogn)\mathcal{O}(m \log n)
Fibonacci Heap O(1)\mathcal{O}(1) O(logn)\mathcal{O}(\log n) O(1)\mathcal{O}(1) O(mlogn)\mathcal{O}(m \log n) O(m+nlogn)\mathcal{O}(m + n \log n)