pgr_prim - pgRouting Manual (3.4)

Description

This algorithm finds the minimum spanning forest in a possibly disconnected graph using Prim’s algorithm.

The main characteristics are:

• It’s implementation is only on undirected graph.

• Process is done only on edges with positive costs.

• When the graph is connected

  • The resulting edges make up a tree

• When the graph is not connected,

  • Finds a minimum spanning tree for each connected component.

  • The resulting edges make up a forest.

• Prim’s running time: \(O(E * log V)\)

• EMPTY SET is returned when there are no edges in the graph.

Signatures

Summary

Example :

Minimum spanning forest of a subgraph

SELECT edge, cost FROM pgr_prim(
  'SELECT id, source, target, cost, reverse_cost
  FROM edges WHERE id < 14'
) ORDER BY edge;
 edge  cost
------+------
    1     1
    2     1
    3     1
    4     1
    6     1
    7     1
    8     1
    9     1
   10     1
   12     1
   13     1
(11 rows)

Parameters

Inner Queries

Result Columns

Returns SET OF (edge, cost)

See Also

• Spanning Tree - Category

• Prim - Family of functions

• The queries use the Sample Data network.

• Boost: Prim’s algorithm documentation

• Wikipedia: Prim’s algorithm

Indices and tables

• Index

• Search Page