# 贪心算法——普林姆算法(Greedy Algorithm-Prim's Algorithm)

xiaoxiao2021-02-28  14

## 贪心算法——普林姆算法(Greedy Algorithm-Prim’s Algorithm)

There is a common situation in which a cashier changes money for customers. Suppose the cashier has paper money denominations 100, 50, 20, 10, 5, 1, 0.5, 0.1 yuan, and we need to change 250 yuan for customers using the smallest number of paper money. How does the cashier make change?

Generally, we want to use as many 100 paper money as we can, then we consider smaller denomination which as 50, 20, 10 and so on until get 250. The priority denomination sequence is 100, 50, 20, 10, 5, 0.5, 0.1. For this scenario, 250= 2*100+50.

The strategy used by the cashier to change is to make decision based on what is the locally best choice.

We hope locally best choices to yield globally best result. This greedy strategy is a very important algorithmic technique, that is Greedy Algorithm.

Although this strategy can not 100% guarantee that, a few famous algorithms has already met this expectation.

We will talk about Prim’s algorithm for solving finding minimum spanning tree in weighted graph and Dijkstra’s algorithm for single-source shortest path.

function Prim(<V, E>) for each v ∈ V do cost[v] ⟵ infinity prev[v] ⟵ null pick initial node v0 cost[v0] ⟵ 0 Q ⟵ initPriorityQueue(V) //key is cost value while Q is non-empty do u ⟵ ejectMin(Q) for each (u, w) ∈ E do if weight(u, w) < cost[w] then cost[w] ⟵ weight(u, w) prev[w] ⟵ v update(Q, w, cost[w])

Java Code

I will update as soon as possible.