Getting Started with pgRouting: Shortest Paths in PostgreSQL

If your application needs to answer “what is the fastest route between two points,” you might reach for an external routing API like Mapbox Directions. But if your spatial data is already stored in PostgreSQL, the Postgres extension pgRouting lets you run graph-based routing queries right where the data is.

PostGIS gives you spatial data types, indexes, and operations like distance calculations, intersections, and buffers, but it has no concept of navigating a network from one point to another. pgRouting fills that gap by adding graph traversal and shortest-path algorithms on top of PostGIS. I recommend it for teams that already use PostGIS and want to keep routing logic close to the data.

pgRouting has been used in a variety of real-world projects. For example, one municipality created real-time emergency vehicle routing, combining open data from the city’s geographic information system with pgRouting to optimize routes for emergency responders.

Prerequisites

You need PostgreSQL with PostGIS and pgRouting installed.

Prepare the packages before installation. On a mac, you can use Homebrew:

brew install postgis
brew install pgrouting
brew install osm2pgrouting
brew install osmium-tool

And then activate the extensions in Postgres:

CREATE EXTENSION postgis;
CREATE EXTENSION pgrouting;

Setting Up a Sample Network

pgRouting operates on a directed graph defined by edges with a source, target, and cost.

Each edge represents a connection between two vertices (intersections, waypoints, or any node in your network). The source and target columns identify the vertices at each end of the edge, and the cost column represents the weight of traversing that edge, which could be distance, travel time, or any metric relevant to your use case. A reverse_cost column allows you to model bidirectional roads or assign different costs for each direction.

First, download an OSM extract for your area from Geofabrik. Then convert it to an osm file, filtering for a single town if desired:

osmium extract -b '-79.1,35.6,-78.9,35.9' north-carolina-260215.osm.pbf -o chapel-hill.osm

Create a database with the PostGIS and pgRouting extensions enabled. Run the import:

osm2pgrouting \
    --file chapel-hill.osm \
    --dbname routing \
    --username your_user \
    --conf /opt/homebrew/share/osm2pgrouting/mapconfig.xml

When you import OSM data with osm2pgrouting, it creates a ways table with columns like id, source, target, length_m, cost_s, reverse_cost_s, geom, and other metadata.

After importing the Chapel Hill OSM extract, the ways table has over 30,000 vertices representing the town’s road network. A vertex might be an intersection, but it could also be a dead end, a point where a road changes speed limit, or anywhere the OSM data was split into segments.

Finding the Shortest Path with pgr_dijkstra

pgr_dijkstra is the foundational routing function. It finds the least-cost path between two vertices using Dijkstra’s algorithm. Dijkstra’s algorithm works by starting at the source vertex and exploring outward, always visiting the lowest-cost unvisited neighbor next. It keeps a running tally of the cheapest known cost to reach each vertex, updating those costs as it discovers shorter paths. This greedy approach guarantees finding the optimal path as long as all edge costs are non-negative, which makes it a natural fit for road networks where distances and travel times are always positive values.

Let’s find the shortest path from the Lumina Theater (vertex 30031) to Weaver Street Market (vertex 30029) in Southern Village. There are multiple routes between these two points, but pgr_dijkstra evaluates all possible paths through the graph and returns only the one with the lowest total cost. The cost_s column in the inner query is what drives that decision – Dijkstra’s algorithm sums up the cost_s values along each candidate path and picks the path with the smallest total.

SELECT seq, path_seq, node, edge, cost AS edge_traversal_cost,
       agg_cost AS total_route_cost
FROM pgr_dijkstra(
    'SELECT id, source, target, cost_s AS cost, reverse_cost_s AS reverse_cost FROM ways',
    30031,  -- Lumina Theater
    30029,  -- Weaver Street Market
    directed := false
);

 seq | path_seq | node  | edge  | edge_traversal_cost |  total_route_cost
-----+----------+-------+-------+---------------------+--------------------
   1 |        1 | 30031 | 37873 |  0.6349355229593167 |                  0
   2 |        2 | 24983 | 29983 |  0.5171508052728394 | 0.6349355229593167
   3 |        3 | 11677 | 20630 |  0.6507623132176732 |  1.152086328232156
   4 |        4 | 22333 | 35060 |  0.5208607405450482 | 1.8028486414498293
   5 |        5 | 30030 | 37872 |   5.963525759114863 | 2.3237093819948775
   6 |        6 | 30029 |    -1 |                   0 |   8.28723514110974
(5 rows)

The result traces a path through five vertices, starting at the Lumina Theater and ending near Weaver Street Market. Each row is one step: the node column is the vertex reached, and edge is the road segment traversed to get there. The edge_traversal_cost is the cost of each individual step, and total_route_cost is the running total.

When to Use pgRouting (and When Not To)

I recommend pgRouting when your road or network data is already in Postgres, when you need routing logic integrated with spatial queries like buffers, intersections, and proximity searches, or when you want full control over cost functions and graph structure.

For moderate-sized networks (tens of thousands of edges), pgRouting performs well and keeps your architecture simple. Road networks are just one application. pgRouting works with any graph that can be expressed as edges with costs, including utility networks (water, gas, electrical grids), hiking and cycling trail systems, river and waterway navigation, indoor routing through building floor plans, and even abstract networks like supply chain logistics or telecommunications infrastructure.

Take a look at the pgRouting documentation for more functions, including driving distance analysis and traveling salesman optimization. If you are already running PostGIS, pgRouting is worth evaluating for your next routing feature.