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
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.
注釈
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.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
注釈
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 | 1195
252963461 | 1461
302056515 | 1256
302057309 | 1639
1645787956 | 856
(5 rows)
id = 1195
.id = 1461
id = 1256
id = 1639
id = 856
The corresponding id
are shown in the following image, and a sample route from the venue to the fish market:
Walking from the Serena hotel to the Venue
1639
to vertex 1195
.length
, which
was calculated by osm2pgrouting, is in unit degrees
.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',
1639, 1195,
directed := false);
注釈
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.Walking from the Serena hotel and from the venue to the botanical garden (in meters).
1639
, 1195
.856
.length_m
.SELECT * FROM pgr_dijkstra(
'SELECT gid AS id,
source,
target,
length_m AS cost
FROM ways',
ARRAY[1639, 1195], 856,
directed := false);
Walking back to the hotel and venue after visiting the botanical garden (in seconds).
856
.1639
, 1195
.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',
856, ARRAY[1639, 1195],
directed := false);
Walking from the hotel or venue to the Botanical garden or the museum (in minutes).
1639
, 1195
.856
, 1256
.s = 1.3 m/s
and t = d/s
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[1639, 1195],
ARRAY[856, 1256],
directed := false)
GROUP BY end_vid
ORDER BY end_vid;
注釈
Inspecting the results, looking for totals (edge = -1):
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
Walking from the hotel or venue to the Botanical garden or the museum (get only the cost in minutes).
1639
, 1195
.856
, 1256
.s = 1.3 m/s
and t = d/s
SELECT *
FROM pgr_dijkstraCost(
'SELECT gid AS id,
source,
target,
length_m / 1.3 / 60 AS cost
FROM ways',
ARRAY[1639, 1195],
ARRAY[856, 1256],
directed := false);
Compare with Exercise 4 『s note.
Walking from the hotel or venue to the Botanical garden or the museum (sumirize cost in minutes).
1639
, 1195
.856
, 1256
.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[1639, 1195],
ARRAY[856, 1256],
directed := false)
GROUP BY end_vid
ORDER BY end_vid;
注釈
An interpretation of the result can be: In general, it is slightly faster to depart from the Venue.