Unsupported versions:2.6 2.5 2.4 2.3 2.2 2.1 2.0
Table of Contents¶
pgRouting extends the PostGIS/PostgreSQL geospatial database to provide geospatial routing and other network analysis functionality.
This is the manual for pgRouting v4.0.0-dev.

The pgRouting Manual is licensed under a Creative Commons Attribution-Share Alike 3.0 License. Feel free to use this material any way you like, but we ask that you attribute credit to the pgRouting Project and wherever possible, a link back to https://pgrouting.org. For other licenses used in pgRouting see the Licensing page.
General¶
Sample Data that is used in the examples of this manual.
Pgrouting Concepts¶
Function Families¶
All Pairs - Family of Functions
pgr_floydWarshall - Floyd-Warshall’s algorithm.
pgr_johnson - Johnson’s algorithm
pgr_aStar - A* algorithm for the shortest path.
pgr_aStarCost - Get the aggregate cost of the shortest paths.
pgr_aStarCostMatrix - Get the cost matrix of the shortest paths.
Bidirectional A* - Family of functions
pgr_bdAstar - Bidirectional A* algorithm for obtaining paths.
pgr_bdAstarCost - Bidirectional A* algorithm to calculate the cost of the paths.
pgr_bdAstarCostMatrix - Bidirectional A* algorithm to calculate a cost matrix of paths.
Bidirectional Dijkstra - Family of functions
pgr_bdDijkstra - Bidirectional Dijkstra algorithm for the shortest paths.
pgr_bdDijkstraCost - Bidirectional Dijkstra to calculate the cost of the shortest paths
pgr_bdDijkstraCostMatrix - Bidirectional Dijkstra algorithm to create a matrix of costs of the shortest paths.
Components - Family of functions
pgr_connectedComponents - Connected components of an undirected graph.
pgr_strongComponents - Strongly connected components of a directed graph.
pgr_biconnectedComponents - Biconnected components of an undirected graph.
pgr_articulationPoints - Articulation points of an undirected graph.
pgr_bridges - Bridges of an undirected graph.
Contraction - Family of functions
Dijkstra - Family of functions
pgr_dijkstra - Dijkstra’s algorithm for the shortest paths.
pgr_dijkstraCost - Get the aggregate cost of the shortest paths.
pgr_dijkstraCostMatrix - Use pgr_dijkstra to create a costs matrix.
pgr_drivingDistance - Use pgr_dijkstra to calculate catchament information.
pgr_KSP - Use Yen algorithm with pgr_dijkstra to get the K shortest paths.
pgr_maxFlow - Only the Max flow calculation using Push and Relabel algorithm.
pgr_boykovKolmogorov - Boykov and Kolmogorov with details of flow on edges.
pgr_edmondsKarp - Edmonds and Karp algorithm with details of flow on edges.
pgr_pushRelabel - Push and relabel algorithm with details of flow on edges.
Applications
pgr_edgeDisjointPaths - Calculates edge disjoint paths between two groups of vertices.
pgr_maxCardinalityMatch - Calculates a maximum cardinality matching in a graph.
pgr_degree - Returns a set of vertices and corresponding count of incident edges to the vertex.
pgr_trsp - Routing with restrictions.
pgr_trspVia - Via Vertices routing with restrictions.
pgr_trsp_withPoints - Vertex/Point routing with restrictions.
pgr_trspVia_withPoints - Via Vertex/point routing with restrictions.
Traveling Sales Person - Family of functions
pgr_TSP - When input is given as matrix cell information.
pgr_TSPeuclidean - When input are coordinates.
pgr_extractVertices - Extracts vertex information based on the edge table information.
pgr_findCloseEdges - Finds close edges of points on the fly
pgr_separateCrossing - Breaks geometries that cross each other.
pgr_separateTouching - Breaks geometries that (almost) touch each other.
withPoints - Family of functions
pgr_withPoints - Route from/to points anywhere on the graph.
pgr_withPointsCost - Costs of the shortest paths.
pgr_withPointsCostMatrix - Costs of the shortest paths.
pgr_withPointsKSP - K shortest paths.
pgr_withPointsDD - Driving distance.
pgr_withPointsVia - Via routing
Functions by categories¶
pgr_drivingDistance - Driving Distance based on Dijkstra’s algorithm
pgr_primDD - Driving Distance based on Prim’s algorithm
pgr_kruskalDD - Driving Distance based on Kruskal’s algorithm
pgr_withPointsDD - Driving Distance based on pgr_withPoints
pgr_KSP - Yen’s algorithm based on pgr_dijkstra
pgr_withPointsKSP - Yen’s algorithm based on pgr_withPoints
withPoints - Family of functions - Functions based on Dijkstra algorithm.
From the TRSP - Family of functions:
pgr_trsp_withPoints - Vertex/Point routing with restrictions.
pgr_trspVia_withPoints - Via Vertex/point routing with restrictions.
Available Functions but not official pgRouting functions¶
Release Notes¶
pgRouting 4.0.0 Release Notes¶
To see all issues & pull requests closed by this release see the Git closed milestone for 4.0.0
Summary of changes by function¶
pgr_aStar
Combinations signature promoted to official.
pgr_aStarCost
Combinations signature promoted to official.
pgr_bdAstar
Combinations signature promoted to official.
pgr_bdAstarCost
Combinations signature promoted to official.
pgr_bdDijkstra
Output columns standardized to
(seq, path_seq, start_vid, end_vid, node, edge, cost, agg_cost)
Combinations signature promoted to official.
pgr_bdDijkstraCost
Combinations signature promoted to official.
pgr_bellmanFord
Output columns standardized to
(seq, path_seq, start_vid, end_vid, node, edge, cost, agg_cost)
pgr_binaryBreadthFirstSearch
Output columns standardized to
(seq, path_seq, start_vid, end_vid, node, edge, cost, agg_cost)
pgr_bipartite
Output columns standardized to
(node, color)
pgr_boykovKolmogorov
Combinations signature promoted to official.
pgr_breadthFirstSearch
:
Standardizing output columns to
(seq, depth, start_vid, pred, node, edge, cost, agg_cost)
pgr_contraction
Breaking change, signatures no longer available:
pgr_contraction(text,bigint[],integer,bigint[],boolean)
pgr_dagShortestPath
Output columns standardized to
(seq, path_seq, start_vid, end_vid, node, edge, cost, agg_cost)
pgr_depthFirstSearch
:
Standardizing output columns to
(seq, depth, start_vid, pred, node, edge, cost, agg_cost)
pgr_dijkstra
Combinations signature promoted to official.
pgr_dijkstraCost
Combinations signature promoted to official.
pgr_edgeColoring
Output columns standardized to
(edge, color)
pgr_edgeDisjointPaths
Output columns standardized to
(seq, path_id, path_seq, start_vid, end_vid, node, edge, cost, agg_cost)
pgr_edmondsKarp
Combinations signature promoted to official.
pgr_edwardMoore
Output columns standardized to
(seq, path_seq, start_vid, end_vid, node, edge, cost, agg_cost)
pgr_KSP
All signatures promoted to official.
pgr_maxFlow
Combinations signature promoted to official.
pgr_pushRelabel
Combinations signature promoted to official.
pgr_sequentialVertexColoring
Output columns standardized to
(node, color)
pgr_topologicalSort
Standardize output to
(seq, node)
pgr_transitiveClosure
Standardized output to
(node,targets)
pgr_trsp
Function promoted to official.
Breaking change, signatures no longer available:
pgr_trsp(text,integer,integer,boolean,boolean,text)
pgr_trsp(text,integer,double precision,integer,double precision,boolean,boolean,text)
pgr_trspVia
Function promoted to official.
Breaking change, signatures no longer available:
pgr_trspviavertices(text,anyarray,boolean,boolean,text)
pgr_trspVia_withPoints
Function promoted to official.
Driving side parameter is positional unnamed and compulsory.
Valid values depend on kind of graph
Breaking change, signatures no longer available:
pgr_trspvia_withpoints(text,text,text,anyarray,boolean,boolean,boolean,character,boolean)
pgr_trspviaedges(text,integer[],double precision[],boolean,boolean,text)
pgr_trsp_withPoints
Function promoted to official.
Driving side parameter is positional unnamed and compulsory.
Valid values depend on kind of graph
Breaking change, signatures no longer available:
pgr_trsp_withpoints(text,text,text,anyarray,anyarray,boolean,character,boolean)
pgr_trsp_withpoints(text,text,text,anyarray,bigint,boolean,character,boolean)
pgr_trsp_withpoints(text,text,text,bigint,anyarray,boolean,character,boolean)
pgr_trsp_withpoints(text,text,text,bigint,bigint,boolean,character,boolean)
pgr_trsp_withpoints(text,text,text,text,boolean,character,boolean)
pgr_turnRestrictedPath
Output columns standardized to
(seq, path_id, path_seq, start_vid, end_vid, node, edge, cost, agg_cost)
pgr_withPoints
Function promoted to official.
Driving side parameter is positional unnamed and compulsory.
Valid values depend on kind of graph
Output columns standardized to
(seq, path_seq, start_vid, end_vid, node, edge, cost, agg_cost)
Breaking change, signatures no longer available:
pgr_withpoints(text,text,anyarray,anyarray,boolean,character,boolean)
pgr_withpoints(text,text,anyarray,bigint,boolean,character,boolean)
pgr_withpoints(text,text,bigint,anyarray,boolean,character,boolean)
pgr_withpoints(text,text,bigint,bigint,boolean,character,boolean)
pgr_withpoints(text,text,text,boolean,character,boolean)
pgr_withPointsCost
Function promoted to official.
Driving side parameter is unnamed and compulsory.
Valid values depend on kind of graph
Output columns standardized to
(start_vid, end_vid, agg_cost)
Breaking change, signatures no longer available:
pgr_withpointscost(text,text,anyarray,anyarray,boolean,character)
pgr_withpointscost(text,text,anyarray,bigint,boolean,character)
pgr_withpointscost(text,text,bigint,anyarray,boolean,character)
pgr_withpointscost(text,text,bigint,bigint,boolean,character)
pgr_withpointscost(text,text,text,boolean,character)
pgr_withPointsCostMatrix
Function promoted to official.
Driving side parameter is positional unnamed and compulsory.
Valid values depend on kind of graph
Output columns standardized to
(start_vid, end_vid, agg_cost)
Breaking change, signatures no longer available:
pgr_withpointscostmatrix(text,text,anyarray,boolean,character)
pgr_withPointsDD
Function promoted to official.
Breaking change, signatures no longer available:
pgr_withpointsdd(text,text,bigint,double precision,boolean,character,boolean)
pgr_withpointsdd(text,text,anyarray,double precision,boolean,character,boolean,boolean)
pgr_withPointsKSP
Function promoted to official.
Breaking change, signatures no longer available:
pgr_withpointsksp(text,text,bigint,bigint,integer,boolean,boolean,character,boolean)
pgr_withPointsVia
Function promoted to official.
Driving side parameter is positional unnamed and compulsory.
Valid values depend on kind of graph
Breaking change, signatures no longer available:
pgr_withpointsvia(text,text,anyarray,boolean,boolean,boolean,character,boolean)
Functions promoted to official¶
Signatures promoted to official¶
#2718 pgr_aStar(Combinations)
#2718 pgr_aStarCost(Combinations)
#2718 pgr_bdAstar(Combinations)
#2718 pgr_bdAstarCost(Combinations)
#2718 pgr_bdDijkstra(Combinations)
#2718 pgr_bdDijkstraCost(Combinations)
#2718 pgr_dijkstra(Combinations)
#2718 pgr_dijkstraCost(Combinations)
#2718 pgr_KSP(All signatures)
#2718 pgr_boykovKolmogorov(Combinations)
#2718 pgr_edmondsKarp(Combinations)
#2718 pgr_maxFlow(Combinations)
#2718 pgr_pushRelabel(Combinations)
SQL signatures and output standardization¶
#2904 Standardize output columns of functions with different output columns within overloads
Standardized to (seq, path_seq, start_vid, end_vid, node, edge, cost, agg_cost)
#2905 pgr_withPoints
#2906 pgr_bdDijkstra
#2907 pgr_bellmanFord
#2908 pgr_binaryBreadthFirstSearch
#2910 pgr_edwardMoore
#2913 pgr_DAGshortestPath
Standardized to (start_vid, end_vid, agg_cost)
Standardized to (seq, path_id, path_seq, start_vid, end_vid, node, edge, cost, agg_cost)
Standardized to (edge, color)
#2924 pgr_edgeColoring
Standardized to (node, color)
Standardized to (seq, depth, start_vid, pred, node, edge, cost, agg_cost)
Standardized to (seq, node)
#2934 pgr_topologicalSort
Standardized to (node,targets)
#2934 pgr_transitiveClosure
Removal of SQL deprecated signatures¶
#2798: pgr_contraction
Breaking change, signatures no longer available:
pgr_contraction(text,bigint[],integer,bigint[],boolean)
#2683: pgr_trsp
Breaking change, signatures no longer available:
pgr_trsp(text,integer,integer,boolean,boolean,text)
pgr_trsp(text,integer,double precision,integer,double precision,boolean,boolean,text)
#2683: pgr_trspVia
Breaking change, signatures no longer available:
pgr_trspviavertices(text,anyarray,boolean,boolean,text)
#2700: pgr_withPointsVia
Breaking change, signatures no longer available:
pgr_withpointsvia(text,text,anyarray,boolean,boolean,boolean,character,boolean)
#2888: pgr_findCloseEdges
pgr_findcloseedges(text,geometry,double precision,integer,boolean,boolean)
pgr_findcloseedges(text,geometry[],double precision,integer,boolean,boolean)
#2890: pgr_withPointsDD
Breaking change, signatures no longer available:
pgr_withpointsdd(text,text,bigint,double precision,boolean,character,boolean)
pgr_withpointsdd(text,text,anyarray,double precision,boolean,character,boolean,boolean)
#2895: pgr_withPointsKSP
Breaking change, signatures no longer available:
pgr_withpointsksp(text,text,bigint,bigint,integer,boolean,boolean,character,boolean)
#2899: pgr_maxCardinalityMatch
Breaking change, signatures no longer available:
pgr_maxCardinalityMatch(text,boolean)
#2901: pgr_TSP
Breaking change, signatures no longer available:
pgr_tsp(text,bigint,bigint,double precision,integer,integer,integer,double precision,double precision,double precision,boolean)
#2901: pgr_TSPeuclidean
Breaking change, signatures no longer available:
pgr_tspeuclidean(text,bigint,bigint,double precision,integer,integer, integer,double precision,double precision,double precision,boolean)
Removal of SQL deprecated functions¶
Removal of SQL deprecated internal functions¶
#2748 _pgr_alphashape(text,double precision)
#2861 _pgr_checkverttab(text,text[],integer,text)
#2861 _pgr_createindex(text,text,text,integer,text)
#2861 _pgr_createindex(text,text,text,text,integer,text)
#2913 _pgr_dagshortestpath(text,anyarray,anyarray,boolean,boolean)
#2913 _pgr_dagshortestpath(text,text,boolean,boolean)
#2730 _pgr_dijkstranear(text,anyarray,anyarray,bigint,boolean)
#2730 _pgr_dijkstranear(text,anyarray,bigint,bigint,boolean)
#2730 _pgr_dijkstranear(text,bigint,anyarray,bigint,boolean)
#2730 _pgr_dijkstra(text,anyarray,anyarray,boolean,boolean,boolean,bigint)
#2730 _pgr_dijkstra(text,anyarray,anyarray,boolean,boolean,boolean,bigint,boolean)
#2730 _pgr_dijkstra(text,text,boolean,boolean,bigint,boolean)
#2730 _pgr_dijkstra(text,text,boolean,boolean,boolean)
#2735 _pgr_drivingdistance(text,anyarray,double precision,boolean,boolean)
#2861 _pgr_endpoint(geometry)
#2861 _pgr_getcolumnname(text,text,integer,text)
#2861 _pgr_getcolumnname(text,text,text,integer,text)
#2861 _pgr_getcolumntype(text,text,integer,text)
#2861 _pgr_getcolumntype(text,text,text,integer,text)
#2861 _pgr_gettablename(text,integer,text)
#2861 _pgr_iscolumnindexed(text,text,integer,text)
#2861 _pgr_iscolumnindexed(text,text,text,integer,text)
#2861 _pgr_iscolumnintable(text,text)
#2745 _pgr_kruskal(text,anyarray,text,bigint,double precision)
#2897 _pgr_ksp(text,anyarray,anyarray,integer,boolean,boolean,boolean)
#2897 _pgr_ksp(text,bigint,bigint,integer,boolean,boolean)
#2897 _pgr_ksp(text,text,integer,boolean,boolean)
#2899 _pgr_maxcardinalitymatch(text,boolean)
#2861 _pgr_msg(integer,text,text)
#2861 _pgr_onerror(boolean,integer,text,text,text,text)
#2861 _pgr_pointtoid(geometry,double precision,text,integer)
#2743 _pgr_prim(text,anyarray,text,bigint,double precision)
#2861 _pgr_quote_ident(text)
#2861 _pgr_startpoint(geometry)
#2683 _pgr_trsp(text,integer,double precision,integer,double precision,boolean,boolean,text)
#2683 _pgr_trsp(text,text,anyarray,anyarray,boolean)
#2683 _pgr_trsp(text,text,anyarray,bigint,boolean)
#2683 _pgr_trsp(text,text,bigint,anyarray,boolean)
#2683 _pgr_trsp(text,text,bigint,bigint,boolean)
#2682 _pgr_trspviavertices(text,integer[],boolean,boolean,text)
#2919 _pgr_trspvia_withpoints(text,text,text,anyarray,boolean,boolean,boolean,character,boolean)
#2919 _pgr_trsp_withpoints(text,text,text,anyarray,anyarray,boolean,character,boolean)
#2919 _pgr_trsp_withpoints(text,text,text,text,boolean,character,boolean)
#2901 _pgr_tspeuclidean(text,bigint,bigint,double precision,integer,integer,integer,double precision,double precision,double precision,boolean)
#2901 _pgr_tsp(text,bigint,bigint,double precision,integer,integer,integer,double precision,double precision,double precision,boolean)
#2861 _pgr_versionless(text,text)
#2890 _pgr_withpointsdd(text,text,anyarray,double precision,boolean,character,boolean,boolean)
#2895 _pgr_withpointsksp(text,text,anyarray,anyarray,integer,character,boolean,boolean,boolean,boolean)
#2895 _pgr_withpointsksp(text,text,bigint,bigint,integer,boolean,boolean,character,boolean)
#2895 _pgr_withpointsksp(text,text,text,integer,character,boolean,boolean,boolean)
#2741 _pgr_withpointsvia(text,bigint[],double precision[],boolean)
#2741 _pgr_withpointsvia(text,text,anyarray,boolean,boolean,boolean,character,boolean)
#2683 _trsp(text,text,anyarray,anyarray,boolean)
#2683 _v4trsp(text,text,anyarray,anyarray,boolean)
#2683 _v4trsp(text,text,text,boolean)
Summary of functions and signatures no longer on pgrouting¶
#2748 pgr_alphashape(geometry,double precision)
#2752 pgr_analyzegraph(text,double precision,text,text,text,text,text)
#2755 pgr_analyzeoneway(text,text[],text[],text[],text[],boolean,text,text,text)
#2798 pgr_contraction(text,bigint[],integer,bigint[],boolean)
#2751 pgr_createtopology(text,double precision,text,text,text,text,text,boolean)
#2827 pgr_createverticestable(text,text,text,text,text)
#2888 pgr_findcloseedges(text,geometry,double precision,integer,boolean,boolean)
#2888 pgr_findcloseedges(text,geometry[],double precision,integer,boolean,boolean)
#2899 pgr_maxcardinalitymatch(text,boolean)
#2886 pgr_nodenetwork(text,double precision,text,text,text,text,boolean)
#2683 pgr_trsp(text,integer,double precision,integer,double precision,boolean,boolean,text)
#2683 pgr_trsp(text,integer,integer,boolean,boolean,text)
#2681 pgr_trspviaedges(text,integer[],double precision[],boolean,boolean,text)
#2682 pgr_trspviavertices(text,anyarray,boolean,boolean,text)
#2919 pgr_trspvia_withpoints(text,text,text,anyarray,boolean,boolean,boolean,character,boolean)
#2919 pgr_trsp_withpoints(text,text,text,anyarray,anyarray,boolean,character,boolean)
#2919 pgr_trsp_withpoints(text,text,text,anyarray,bigint,boolean,character,boolean)
#2919 pgr_trsp_withpoints(text,text,text,bigint,anyarray,boolean,character,boolean)
#2919 pgr_trsp_withpoints(text,text,text,bigint,bigint,boolean,character,boolean)
#2919 pgr_trsp_withpoints(text,text,text,text,boolean,character,boolean)
#2901 pgr_tspeuclidean(text,bigint,bigint,double precision,integer,integer,integer,double precision,double precision,double precision,boolean)
#2901 pgr_tsp(text,bigint,bigint,double precision,integer,integer,integer,double precision,double precision,double precision,boolean)
#2919 pgr_withpointscostmatrix(text,text,anyarray,boolean,character)
#2919 pgr_withpointscost(text,text,anyarray,anyarray,boolean,character)
#2919 pgr_withpointscost(text,text,anyarray,bigint,boolean,character)
#2919 pgr_withpointscost(text,text,bigint,anyarray,boolean,character)
#2919 pgr_withpointscost(text,text,bigint,bigint,boolean,character)
#2919 pgr_withpointscost(text,text,text,boolean,character)
#2890 pgr_withpointsdd(text,text,anyarray,double precision,boolean,character,boolean,boolean)
#2890 pgr_withpointsdd(text,text,bigint,double precision,boolean,character,boolean)
#2895 pgr_withpointsksp(text,text,bigint,bigint,integer,boolean,boolean,character,boolean)
#2919 pgr_withpoints(text,text,anyarray,anyarray,boolean,character,boolean)
#2919 pgr_withpoints(text,text,anyarray,bigint,boolean,character,boolean)
#2919 pgr_withpoints(text,text,bigint,anyarray,boolean,character,boolean)
#2919 pgr_withpoints(text,text,bigint,bigint,boolean,character,boolean)
#2919 pgr_withpoints(text,text,text,boolean,character,boolean)
#2919 pgr_withpointsvia(text,text,anyarray,boolean,boolean,boolean,character,boolean)
Code enhancements¶
Removal of unused C/C++ code
Refactor the Script to build the update PostgreSQL file.
One process & driver for:
allpairs: johnson and Floyd-Warshall
Shortest path: Dijkstra and withPoints using Dijkstra
Deprecation of internal C/C++ functions
Deprecated functions are substituted by new function.
_pgr_drivingdistance => _pgr_drivingdistancev4
_pgr_withpointsdd => _pgr_withpointsddv4
_pgr_kruskal => _pgr_kruskalv4
_pgr_prim => _pgr_primv4
_pgr_dijkstra => _pgr_dijkstra_v4
_pgr_withpointsksp => _pgr_withpointsksp_v4
_pgr_trspvia_withpoints => _pgr_trspvia_withpoints_v4
_pgr_trsp_withpoints => _pgr_trsp_withpoints_v4
_pgr_withpointsvia => _pgr_withpointsvia_v4
Internal C/C++ functions in legacy
#2683 _trsp
#2683 _v4trsp
#2683 _v4trsp
#2748 _pgr_alphashape
#2913 _pgr_dagshortestpath
All releases¶
Indices and tables