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.
- 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.
- 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.
