Prim's Algorithm: Difference between revisions

From NovaOrdis Knowledge Base
Jump to navigation Jump to search
 
(31 intermediate revisions by the same user not shown)
Line 3: Line 3:
* https://en.wikipedia.org/wiki/Prim's_algorithm
* https://en.wikipedia.org/wiki/Prim's_algorithm
=Internal=
=Internal=
* [[Graph_Concepts#Minimum_Spanning_Tree_.28MST.29|Graph Concepts]]
* [[The Minimum Spanning Tree Problem|The Minimum Spanning Tree Problem]]
* [[The Minimum Spanning Tree Problem|The Minimum Spanning Tree Problem]]
* [[Dijkstra%27s_Shortest-Path_Algorithm|Dijkstra's Shortest-Path Algorithm]]
* [[Algorithms#Greedy_Algorithms|Greedy Algorithms]]
=Overview=
=Overview=
Prim's algorithm is a [[Algorithms#Greedy_Algorithms|greedy algorithm]] that computes the [[The_Minimum_Spanning_Tree_Problem|minimum cost spanning tree]] of a an undirected graph. Even if the algorithm was named after Prim, it was discovered earlier by Jarník. The algorithm is similar to [[Dijkstra%27s_Shortest-Path_Algorithm|Dijkstra's shortest-path algorithm]].
Prim's algorithm is a [[Algorithms#Greedy_Algorithms|greedy algorithm]] that computes the [[The_Minimum_Spanning_Tree_Problem|minimum cost spanning tree (MST)]] of a an undirected graph. Even if the algorithm was named after Prim, it was discovered earlier by Jarník. The algorithm is similar to [[Dijkstra%27s_Shortest-Path_Algorithm|Dijkstra's shortest-path algorithm]] in that it iterates over the all nodes of the graph, one node at a time ("growing the explored territory like a mold from a starting point"), always maintaining connectivity, evaluating all edges that cross the cut formed by the explored territory and the unexplored territory, attempting to find the cheapest edge. The cost of the edge is the [[Algorithms#Greedy_Score|greedy score]]. Once the edge is found, the distant vertex is added to the "explored territory". There is a [[#Non-Optimized_Implementation|non-optimized implementation]], where all possible edges are evaluated at each step, and whose running time is O(m n), and an [[Prim%27s_Algorithm#Optimized_Implementation|optimized implementation]] that uses heaps, whose running time is O(m log n). An alternative algorithm to compute the minimum spanning tree is [[Kruskal's Algorithm|Kruskal's algorithm]].


=Non-Optimized Implementation=
=Non-Optimized Implementation=


The Prim algorithm randomly selects a node. It then enters a loop where at each iteration adds a new edge and spans one new vertex, adjacent to the ones already spanning. The new vertex added to the "explored territory" is selected so it can be reached via the cheapest edge. This is what makes Prim's algorithm a [[Algorithms#Greedy_Algorithms|greedy algorithm]].
The Prim algorithm randomly selects a node. It then enters a loop where at each iteration adds a new edge and spans one new vertex, adjacent to the ones already spanning. The new vertex added to the "explored territory" is selected so it can be reached via the cheapest edge. This is what makes Prim's algorithm a [[Algorithms#Greedy_Algorithms|greedy algorithm]].
The running time of the non-optimized implementation is O(m n).
<font size=-1>
<font size=-1>
   Initialize X={s} <font color=teal># X is the set of vertices that we spanned so far
   Initialize X={s} <font color=teal># X is the set of vertices that we spanned so far, s ∈ V chosen arbitrarily</font>
                  # s ∈ V chosen arbitrarily</font>
   Initialize T=<font color=teal># T is the minimum spanning tree built so far. Invariant: X = vertices spanned by the three-so-far T</font>  
   Initialize A[s]={0} <font color=teal># A maintains computed shortest path distances from the vertices explored so far to s</font>
  Initialize B[s]={empty path} <font color=teal># B maintains the actual shortest path distances from the vertices explored
                              # so far to s. This is not necessary in the algorithm but helps with the
                              # understanding of the algorithm.</font>
   while X ≠ V: <font color=teal># The main loop, each iteration grows X with one node</font>
   while X ≠ V: <font color=teal># The main loop, each iteration grows X with one node</font>
       for every directed edge (v, w) ∈ E that crosses X/(V-X) boundary v ∈ V, w ∈ V-X
       let e=(u,v) be the cheapest edge of G with u ∈ X, v X
          pick the (v<sup>*</sup>, w<sup>*</sup>) edge that minimizes A[v] + ℓ<sub>vw</sub> <font color=teal># The Dijkstra's Greedy Criterion</font>
       add e to T
       add w<sup>*</sup> to X
       add v to X
       set A[w<sup>*</sup>] = A[v<sup>*</sup>] + ℓ<sub>v<sup>*</sup>w<sup>*</sup></sub>
      set B[w<sup>*</sup>] = B[v<sup>*</sup>] ⋃ (v<sup>*</sup>,w<sup>*</sup>)
</font>
</font>
==Playground Implementation==
{{External|https://github.com/ovidiuf/playground/blob/master/learning/stanford-algorithms-specialization/10-prim-algorithm/src/main/java/playground/stanford/prim/PrimAlgorithm.java}}
=Correctness Proof=
The Prim's algorithm always computes a MST.
{{External|https://www.coursera.org/learn/algorithms-greedy/lecture/15UXn/correctness-proof-i}}
{{External|https://www.coursera.org/learn/algorithms-greedy/lecture/hYzal/correctness-proof-ii}}
=Optimized Implementation=
The optimized implementation uses [[Heap#Canonical_Uses_of_a_Heap|heaps]], in a similar manner to [[Dijkstra%27s_Shortest-Path_Algorithm|Dijkstra's shortest-path algorithm]].
{{External|https://www.coursera.org/learn/algorithms-greedy/lecture/bYMq1/fast-implementation-i}}
{{External|https://www.coursera.org/learn/algorithms-greedy/lecture/qzdR8/fast-implementation-ii}}

Latest revision as of 16:53, 22 October 2021

External

Internal

Overview

Prim's algorithm is a greedy algorithm that computes the minimum cost spanning tree (MST) of a an undirected graph. Even if the algorithm was named after Prim, it was discovered earlier by Jarník. The algorithm is similar to Dijkstra's shortest-path algorithm in that it iterates over the all nodes of the graph, one node at a time ("growing the explored territory like a mold from a starting point"), always maintaining connectivity, evaluating all edges that cross the cut formed by the explored territory and the unexplored territory, attempting to find the cheapest edge. The cost of the edge is the greedy score. Once the edge is found, the distant vertex is added to the "explored territory". There is a non-optimized implementation, where all possible edges are evaluated at each step, and whose running time is O(m n), and an optimized implementation that uses heaps, whose running time is O(m log n). An alternative algorithm to compute the minimum spanning tree is Kruskal's algorithm.

Non-Optimized Implementation

The Prim algorithm randomly selects a node. It then enters a loop where at each iteration adds a new edge and spans one new vertex, adjacent to the ones already spanning. The new vertex added to the "explored territory" is selected so it can be reached via the cheapest edge. This is what makes Prim's algorithm a greedy algorithm.

The running time of the non-optimized implementation is O(m n).

 Initialize X={s} # X is the set of vertices that we spanned so far, s ∈ V chosen arbitrarily
 Initialize T=∅ # T is the minimum spanning tree built so far. Invariant: X = vertices spanned by the three-so-far T 
 while X ≠ V: # The main loop, each iteration grows X with one node
     let e=(u,v) be the cheapest edge of G with u ∈ X, v ∉ X
     add e to T
     add v to X

Playground Implementation

https://github.com/ovidiuf/playground/blob/master/learning/stanford-algorithms-specialization/10-prim-algorithm/src/main/java/playground/stanford/prim/PrimAlgorithm.java

Correctness Proof

The Prim's algorithm always computes a MST.

https://www.coursera.org/learn/algorithms-greedy/lecture/15UXn/correctness-proof-i
https://www.coursera.org/learn/algorithms-greedy/lecture/hYzal/correctness-proof-ii

Optimized Implementation

The optimized implementation uses heaps, in a similar manner to Dijkstra's shortest-path algorithm.

https://www.coursera.org/learn/algorithms-greedy/lecture/bYMq1/fast-implementation-i
https://www.coursera.org/learn/algorithms-greedy/lecture/qzdR8/fast-implementation-ii