Prim's Algorithm: Difference between revisions
Jump to navigation
Jump to search
| Line 5: | Line 5: | ||
* [[The Minimum Spanning Tree Problem|The Minimum Spanning Tree Problem]] | * [[The Minimum Spanning Tree Problem|The Minimum Spanning Tree Problem]] | ||
=Overview= | =Overview= | ||
Even if the algorithm was named after Prim, it was discovered earlier by Jarník. | 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]]. | ||
=Non-Optimized Implementation= | =Non-Optimized Implementation= | ||
The Prim algorithm randomly selects a node and then, in a loop where at each iteration a new node is added to the "explored territory", it selects the node that can be reached via the cheapest edge. | The Prim algorithm randomly selects a node and then, in a loop where at each iteration a new node is added to the "explored territory", it selects the node that can be reached via the cheapest edge. | ||
Revision as of 22:04, 20 October 2021
External
- https://www.coursera.org/learn/algorithms-greedy/lecture/tQ6gK/prims-mst-algorithm
- https://en.wikipedia.org/wiki/Prim's_algorithm
Internal
Overview
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 and then, in a loop where at each iteration a new node is added to the "explored territory", it selects the node that can be reached via the cheapest edge.