Greedy

Greedy

- Like DP or Divide&Conquer, Greedy is a programming paradigm rather than a specific algorithm.

 

 

Minimum Spanning Tree

- Let's assume we have a connected, undirected graph G=(V,E) with weight function w : E -> R.

- The MST of the graph is a tree that connects all vertices with minimum weight.

- An algorithm that finds the MST of a graph could be used when building Spanning Tree Protocol(STP) in networks.

- Such problem has a optimal substructure, assuming we have a MST, if we delete one edge, each subtree will be the MST of each subgraph.

- Since the problem of finding a MST given a graph has properties of Overlapping Subproblem and Optimal Substructure, we could solve it via Dynamic Programming.

 

- However, there is one more property that leads to solve the problem with Greedy approach.

- Greedy-Choice Property is a property that helds if a locally optimal choice is gobally optimal.

 

- Maintaining a priority queue Q, push each vertex in Q with the weight of the least weight edge connecting it to a vertex in A.

Pseudo-code for MST Construction (Prim Algorithm)

- The upper three lines could be done in O(V)*(Extract-Min) time.

- The while loop will be executed |V| times and in each execution the for loop will be executed degree(u) times.

- Due to Handshaking Lemma, the total number of execution of for loop within while loop will be O(E) times.

- The total runtime is O(V)*(Extract-Min) + O(E)*(Decrease-Key).

 

- Different choices of priority queue Q will lead to different run-time.

- We could make different choice based on E,V.

 

- In Greedy Algorithms, the Greedy choice property does not imply recurrence tree.

- This is the main difference with Dynamic Programming.

 

 

Shortest Path

- One example where Greedy Algorithm could be applied to is finding the Shortest Path in Graph.

- Let's consider a digraph G=(V,E) with edge-weight function w:E->R .

- The weight of path p=v1 -> v2 -> ... -> vk is to be defined as the figure below.

- The shortest path from u to v is a path of minimum weight from u to v.

- If a graph G contains a negative-weight cycle, then some shortest paths do not exist.

- Let's maintain a set S of vertices whose shortest-path distances from s are knwown.

- At each step, add to S the vertex v from V-S whose distance estimate from s is minimum.

- Then update the distance estimates of vertices adjacent to v.

Pseudo-code for Finding the Shortest Path in a graph (Dijkstra's Algorithm)

- We can prove that d maintains the shortest path value from starting node by using contradiction.

 

- The runtime is similar to the analysis of Prim's MST algorithm.

- The for loop within the while loop runs for total E times due to Handshaking Lemma.

- The total runtime is O(V)*(Extract-Min) + O(E)*(Decrease-Key).

 

- Different choices of priority queue Q will lead to different run-time.

 

 

SPFA

- SPFA Algorithm is a more enhanced Shortest Path Finding Algorithm.

- SPFA works better than Dijkstra if the number of edges are very sparse.

- The worst time complexity is the same, but has better average time complexity.

 

- The key idea is not to put a new node into the queue if it is already pushed into the queue.

Pseudo-Code for SPFA Algorithm