The Jarník-Prim algorithm (Jarník's algorithm, Prim's algorithm, DJP algorithm) is used to find a minimum/maximum spanning tree of the graph (spanning tree, in which is the sum of its edges weights minimal/maximal). The algorithm was developed in 1930 by Czech mathematician Vojtěch Jarník, in 1957 it was rediscovered by American mathematician Robert Prim. And again in 1959 the algorithm was rediscovered by Dutch computer scientist Edsger Dijkstra.
The algorithm traverses the graph starting at a random node and maintains a list of already discovered nodes with their distance from the already connected (processed) subgraph. In every step the procedure connects a node, which is in the least distance, discovers its neighbours or recalculates their distance, if they had been already discovered and a more favorable edge was found. When all the nodes are connected to the subgraph, the algorithm terminates.
The complexity of the Jarník-Prim algorithm is dependent on the implementation of the list. The list itself may be modified at most times, because every discovery of a new edge may add a new node to the list or change a weight of some already discovered node.
If we implement the list using a binary heap, which acts as a priority queue, than its each modification takes steps. Hence the complexity of the Jarník-Prim algorithm is .
/** * Jarnik-Prim algorithm * Finds the minimal spanning tree of the given graph * @graph graph * @weight edge weights * @return array of predecessors */ node jarnikPrimAlgorithm(graph, weight) Queue q q.addAllVetices(graph.vertices) //add all vertices to the queue distances = new int[q.size()] //array of distances distances = 0 //root for i in 1 -> distances.length - 1 do distances[i] = +inf //all remaining vertices are in infinite distance predecessors = new node[q.size()] //array of predecessors predecessors = null //the root does not have any predecessor while !queue.empty() do //while the queue is not empty u = queue.extractMin() //return a node in a minimal distance for node in descendants(u) do //for all descendants of u if queue.contains(node) AND weight(u, node) < d[node] //if we have found some improving path to the descendant then predecessors[node] = u //than u is his predecessor d[node] = weight(u, node) //and set a new distance return predecessors //return the array of predecessors
- KOLÁŘ, Josef. Teoretická informatika. 2. edition. Prague : Česká informatická společnost, 2004. 205 p. ISBN 80-900853-8-5.