pgr_prim - pgRouting Manual (3.2)

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

pgr_prim(edges_sql)

RETURNS SET OF (edge, cost)
OR EMPTY SET

Example :

Minimum Spanning Forest of a subgraph

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

Parameters

Inner query

Where:

ANY-INTEGER :

SMALLINT, INTEGER, BIGINT

ANY-NUMERICAL :

SMALLINT, INTEGER, BIGINT, REAL, FLOAT

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