5. pgRouting Algorithms

../_images/route.png

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.

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. You can specify when to consider the graph as directed or undirected.

Signature Summary

pgr_dijkstra(edges_sql, start_vid,  end_vid)
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 any 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 implemeted 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 Dar Es Salaam event are going to be used. These locations are within this area http://www.openstreetmap.org/#map=16/-6.8139/39.2976

Note

Connect to the database with if not connected:

psql city_routing

SELECT osm_id, id FROM ways_vertices_pgr
      WHERE osm_id IN (252643343, 1645787956, 302056515, 252963461, 302057309)
      ORDER BY osm_id;
   osm_id   |  id
------------+------
  252643343 | 1661
  252963461 | 2759
  302056515 |  115
  302057309 | 1060
 1645787956 | 1253
(5 rows)
  • 252643343, Intersection near the entrance to the venue, at the Shaaban Robert Street & Ghana street id = 1661.
  • 252963461 National Museum and House of Culture with id = 2759
  • 302056515 Fish market and the beach id = 115
  • 302057309 Serena Hotel with id = 1060
  • 1645787956 entrance of the botanical garden id = 1253

The corresponding id are shown in the following image, and a sample route from the venue to the fish market:

../_images/route.png

5.1.1. Exercise 1 - Single pedestrian routing.

Walking from the Serena hotel to the Venue

From the Serena Hotel, going to the Venue
  • The pedestrian wants to go from vertex 1060 to vertex 1661.
  • 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',
    1060, 1661,
    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 Serena hotel and from the venue to the botanical garden (in meters).

From the hotel & venue, to/from the botanical garden
  • The pedestrians are departing at vertices 1060, 1661.
  • All pedestrians want to go to vertex 1253.
  • 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[1060, 1661], 1253,
    directed := false);

Solution to Exercise 2

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

Walking back to the hotel and venue after visiting the botanical garden (in seconds).

From the hotel & venue, to/from the botanical garden
  • All pedestrians are departing from vertex 1253.
  • Pedestrians want to go to locations 1060, 1661.
  • 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',
    1253, ARRAY[1060, 1661],
    directed := false);

Solution to Exercise 3

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

Walking from the hotel or venue to the Botanical garden or the museum (in minutes).

From the hotels & venue, to sighseen
  • The pedestrians depart from 1060, 1661.
  • The pedestrians want to go to destinations 1253, 115.
  • 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 end_vid, sum(agg_cost)
FROM pgr_dijkstraCost(
    'SELECT gid AS id,
    source,
    target,
    length_m  / 1.3 / 60 AS cost
    FROM ways',
    ARRAY[1060, 1661],
    ARRAY[1253, 115],
    directed := false)
GROUP BY end_vid
ORDER BY end_vid;

Solution to Exercise 4

Note

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

  • Going to vertex 1253:
    • from 1661 takes 7.58936281639964 minutes (row 4)
    • from 1060 takes 14.1217680758304 minutes (row 23)
  • Going to to vertex 115:
    • from 1661 takes 20.5968484435532 minutes (row 16)
    • from 1060 takes 26.7767911805329 minutes (row 39)

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)
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.

From the hotels & venue, to sighseen

Walking from the hotel or venue to the Botanical garden or the museum (get only the cost in minutes).

  • The pedestrians depart from 1060, 1661.
  • The pedestrians want to go to destinations 1253, 115.
  • 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[1060, 1661],
    ARRAY[1253, 115],
    directed := false);

Solution to Exercise 5

Compare with Exercise 4 ‘s note.

5.2.2. Exercise 6 - Many Pedestrians going to different destinations sumirizes the total costs per destination.

Walking from the hotel or venue to the Botanical garden or the museum (sumirize cost in minutes).

  • The pedestrians depart from 1060, 1661.
  • The pedestrians want to go to destinations 1253, 115.
  • 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 end_vid, sum(agg_cost)
FROM pgr_dijkstraCost(
    'SELECT gid AS id,
    source,
    target,
    length_m  / 1.3 / 60 AS cost
    FROM ways',
    ARRAY[1060, 1661],
    ARRAY[1253, 115],
    directed := false)
GROUP BY end_vid
ORDER BY end_vid;

Solution to Exercise 6

Note

An interpretation of the result can be: In general, it is slightly faster to depart from the Venue.