5. pgRouting Algorithms ¶

pgRouting was first called pgDijkstra, because it implemented only shortest path search with Dijkstra algorithm. Later other functions were added and the library was renamed to pgRouting.

Chapter Contents

pgRouting Algorithms
- pgr_dijkstra
- pgr_dijkstraCost
  - Exercise 5 - Many Pedestrians going to different destinations returning aggregate costs.
  - Exercise 6 - Many Pedestrians going to different destinations summarizing the total costs per departure.

5.1. pgr_dijkstra ¶

Dijkstra algorithm was the first algorithm implemented in pgRouting. It doesn’t require other attributes than id, source and target ID and cost and reverse_cost.

You can specify when to consider the graph as directed or undirected.

Signature Summary

pgr_dijkstra(edges_sql, start_vid,  end_vid  [, directed])
pgr_dijkstra(edges_sql, start_vid,  end_vids [, directed])
pgr_dijkstra(edges_sql, start_vids, end_vid  [, directed])
pgr_dijkstra(edges_sql, start_vids, end_vids [, directed])

RETURNS SET OF (seq, path_seq [, start_vid] [, end_vid], node, edge, cost, agg_cost)
    OR EMPTY SET

Description of the parameters can be found in pgr_dijkstra.

Note

Many pgRouting functions have sql::text as one of their arguments. While this may look confusing at first, it makes the functions very flexible as the user can pass a SELECT statement as function argument as long as the returned result contains the required number of attributes and the correct attribute names.
Most of pgRouting implemented algorithms do not require the network geometry.
Most of pgRouting functions do not return a geometry, but only an ordered list of nodes or edges.

Identifiers for the Queries

The assignment of the vertices identifiers on the source and target columns may be different, the following exercises will use the results of this query. For the workshop, some locations near of the FOSS4G Bucharest event are going to be used. These locations are within this area http://www.openstreetmap.org/#map=14/44.4291/26.0854

255093299 Hotel Capitol
6159253045 Little Bucharest Hostal
6498351588 venue at National Theater Bucharest
123392877 workshops at Faculty of Geography of the University of Bucharest
1886700005 Parliament House

Connect to the database, if not connected:

psql city_routing

Get the vertex identifiers

SELECT osm_id, id FROM ways_vertices_pgr
WHERE osm_id IN (123392877, 255093299, 1886700005, 6159253045, 6498351588)
ORDER BY osm_id;

   osm_id   |  id   
------------+-------
  123392877 |  2340
  255093299 |   279
 1886700005 |  1442
 6159253045 | 13734
 6498351588 | 16826
(5 rows)

255093299 Hotel Capitol (279)
6159253045 Little Bucharest Hostal (13734)
6498351588 venue at National Theater Bucharest (16826)
123392877 workshops at Faculty of Geography of the University of Bucharest (2340)
1886700005 Parliament House (1442)

The corresponding id are shown in the following image, and a sample route from venue at National Theater Bucharest to Parliament House

5.1.1. Exercise 1 - Single pedestrian routing.¶

Walking from Hotel Capitol to the venue at National Theater Bucharest

The pedestrian wants to go from vertex 279 to vertex 16826.
The pedestrian’s cost is in terms of length. In this case length, which was calculated by osm2pgrouting, is in unit degrees.
From a pedestrian perspective the graph is undirected, that is, the pedestrian can move in both directions on all segments.

SELECT * FROM pgr_dijkstra(
    '
      SELECT gid AS id,
        source,
        target,
        length AS cost
      FROM ways
    ',
    279,
    16826,
    directed := false);

Solution to Exercise 1

Note

The returned cost attribute represents the cost specified in the inner SQL query (edges_sql::text argument). In this example cost is length in unit “degrees”. Cost may be time, distance or any combination of both or any other attributes or a custom formula.
node and edge results may vary depending on the assignment of the identifiers to the vertices given by osm2pgrouting.

5.1.2. Exercise 2 - Many Pedestrians going to the same destination.¶

Walking from the Hotel Capitol and Little Bucharest Hostal to the venue at National Theater Bucharest

From |place_1| and |place_2| to |place_3|

The pedestrians are departing at vertices 279 and 13734
All pedestrians want to go to vertex 16826
The cost to be in meters using attribute length_m.

SELECT * FROM pgr_dijkstra(
    '
      SELECT gid AS id,
        source,
        target,
        length_m AS cost
      FROM ways
    ',
    ARRAY[279,13734],
    16826,
    directed := false);

Solution to Exercise 2

5.1.3. Exercise 3 - Many Pedestrians departing from the same location.¶

Walking from the venue at National Theater Bucharest to the Hotel Capitol and Little Bucharest Hostal (in seconds).

All pedestrians are departing from vertex 16826
Pedestrians want to go to locations 279 and 13734
The cost to be in seconds, with a walking speed s = 1.3 m/s and t = d/s

SELECT * FROM pgr_dijkstra(
    '
      SELECT gid AS id,
        source,
        target,
        length_m / 1.3 AS cost
      FROM ways
    ',
    16826,
    ARRAY[279,13734],
    directed := false);

Solution to Exercise 3

5.1.4. Exercise 4 - Many Pedestrians going to different destinations.¶

Walking from the hotels to the workshops at Faculty of Geography of the University of Bucharest and Parliament House (in minutes).

From the hotels to the |place_4| and |place_5|

The pedestrians depart from 279 and 13734
The pedestrians want to go to destinations 2340 and 1442
The cost to be in minutes, with a walking speed s = 1.3 m/s and t = d/s
Result adds the costs per destination.

SELECT * FROM pgr_dijkstra(
    '
      SELECT gid AS id,
       source,
       target,
       length_m / 1.3 / 60 AS cost
      FROM ways
    ',
    ARRAY[279,13734],
    ARRAY[2340, 1442],
    directed := false);

Solution to Exercise 4

Note

Inspecting the results, looking for totals (edge = -1):

Going to vertex 2340:
- from 279 takes 6.67.. minutes (seq = 72)
- from 13734 takes 6.92.. minutes (seq = 141)
Going to to vertex 1442:
- from 279 takes 19.69.. minutes (seq = 43)
- from 13734 takes 17.26.. minutes (seq = 122)

5.2. pgr_dijkstraCost ¶

When the main goal is to calculate the total cost, without “inspecting” the pgr_dijkstra results, using pgr_dijkstraCost returns a more compact result.

Signature Summary

pgr_dijkstraCost(edges_sql, start_vid,  end_vid  [, directed])
pgr_dijkstraCost(edges_sql, start_vid,  end_vids [, directed])
pgr_dijkstraCost(edges_sql, start_vids, end_vid  [, directed])
pgr_dijkstraCost(edges_sql, start_vids, end_vids [, directed])

RETURNS SET OF (start_vid, end_vid, agg_cost)
    OR EMPTY SET

Description of the parameters can be found in pgr_dijkstraCost

5.2.1. Exercise 5 - Many Pedestrians going to different destinations returning aggregate costs.¶

Walking from the hotels to the workshops at Faculty of Geography of the University of Bucharest or Parliament House (get only the cost in minutes).

The pedestrians depart from 279 and 13734
The pedestrians want to go to destinations 2340 and 1442
The cost to be in minutes, with a walking speed s = 1.3 m/s and t = d/s
Result as aggregated costs.

SELECT *
FROM pgr_dijkstraCost(
    '
      SELECT gid AS id,
       source,
       target,
       length_m  / 1.3 / 60 AS cost
      FROM ways
    ',
    ARRAY[279,13734],
    ARRAY[2340, 1442],
    directed := false);

Solution to Exercise 5

Compare with Exercise 4 ‘s note.

5.2.2. Exercise 6 - Many Pedestrians going to different destinations summarizing the total costs per departure.¶

Walking from the hotels to the workshops at Faculty of Geography of the University of Bucharest or Parliament House (summarize cost in minutes).

The pedestrians depart from 279 and 13734
The pedestrians want to go to destinations 2340 and 1442
The cost to be in minutes, with a walking speed s = 1.3 m/s and t = d/s
Result adds the costs per destination.

SELECT start_vid, sum(agg_cost)
FROM pgr_dijkstraCost(
    '
      SELECT gid AS id,
        source,
        target,
        length_m  / 1.3 / 60 AS cost
      FROM ways
    ',
    ARRAY[279,13734],
    ARRAY[2340, 1442],
    directed := false)
GROUP BY start_vid
ORDER BY start_vid;

Solution to Exercise 6

Note

An interpretation of the result can be: In general, it is faster to depart from the Little Bucharest Hostal than from the Hotel Capitol