Prim's Algorithm: Difference between revisions

From NovaOrdis Knowledge Base
Jump to navigation Jump to search
Line 10: Line 10:


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]].
<font size=-1>
  Initialize X={s} <font color=teal># X is the set of vertices that we spanned so far
                  # s ∈ V chosen arbitrarily</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>
      for every directed edge (v, w) ∈ E that crosses X/(V-X) boundary v ∈ V, w ∈ 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 w<sup>*</sup> 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>

Revision as of 22:13, 20 October 2021

External

Internal

Overview

Prim's algorithm is a greedy algorithm that computes the 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's shortest-path 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.

 Initialize X={s} # X is the set of vertices that we spanned so far
                  # s ∈ V chosen arbitrarily
 Initialize A[s]={0} # A maintains computed shortest path distances from the vertices explored so far to s
 Initialize B[s]={empty path} # 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.

 while X ≠ V: # The main loop, each iteration grows X with one node
     for every directed edge (v, w) ∈ E that crosses X/(V-X) boundary v ∈ V, w ∈ V-X
         pick the (v*, w*) edge that minimizes A[v] + ℓvw # The Dijkstra's Greedy Criterion
     add w* to X
     set A[w*] = A[v*] + ℓv*w*
     set B[w*] = B[v*] ⋃ (v*,w*)