Prims Algorithm: Difference between revisions
From Rice Wiki
No edit summary |
No edit summary |
||
Line 32: | Line 32: | ||
smallest edge that crosses the cut from <math>A = r</math> and <math>V - | smallest edge that crosses the cut from <math>A = r</math> and <math>V - | ||
r</math>. | r</math>. | ||
Given an optimal solution with (r,y), prove that <math>A = OPT - (r,y) + | |||
(r, x)</math> is still optimal. | |||
<math>A</math> is still a tree since there is no cycles created. | |||
<math>w(r,y) \geq w(r,x)</math> due to its properties as the greedy | |||
choice. | |||
Therefore, <math>A</math> must be optimal. | |||
[[Category:Algorithms]] | [[Category:Algorithms]] |
Revision as of 01:39, 8 March 2024
Approach: Greedy
Implementation
for each u in V: key[u] = infinity // cost array pi[u] = infinity // from array Q = new PriorityQueue(V) key[root] = 0 while Q is not empty: u = extractMin(Q) # Reduce nodes for v in adj[u]: if v in Q and w[u,v] < key[v]: key[v] = w[u,v]
Analysis
Priority queue is slower than array when the graph is dense, so sometimes it's better to use Dijsktra's algorithm.
Proof: Greedy
Greeedy strategy: Let the greedy choice be the edge that is smallest that crosses the cut between and .
Name greedy choice: let be the smallest edge that crosses the cut from and .
Given an optimal solution with (r,y), prove that is still optimal.
is still a tree since there is no cycles created.
due to its properties as the greedy choice.
Therefore, must be optimal.