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.

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 of the FOSS4G Boston event are going to be used. These locations are within this area http://www.openstreetmap.org/#map=14/42.3526/-71.0502

Note

Connect to the database with if not connected:

```
psql city_routing
```

```
SELECT osm_id, id FROM ways_vertices_pgr
WHERE osm_id IN (61350413, 61441749, 61479912, 61493634, 1718017636, 2481136250)
ORDER BY osm_id;
osm_id | id
------------+-------
61350413 | 3986
61441749 | 4793
61479912 | 13009
61493634 | 12235
1718017636 | 9411
2481136250 | 8401
(6 rows)
```

- 61350413 is the entrance to the venue, at the Seaport Hotel & World Trade Center with
`id = 3986`

. - 61441749 is the Central Parking at the Airport with
`id = 4793`

- 61479912 is the Harpoon Brewery with
`id = 13009`

- 61493634 is the Market Place with
`id = 12235`

- 1718017636 is the Westin Boston Waterfront with
`id = 9411`

- 2481136250 is the New England Aquarium with
`id = 8401`

The corresponding `id`

are shown in the following image, and a sample route from the venue to the airport:

Walking from the Westin hotel to the Venue

- The pedestrian wants to go from vertex
`9411`

to vertex`3986`

. - 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',
9411, 3986,
directed := false);
```

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.

Walking from the Westin and Seaport hotels to the brewry (in meters).

- The pedestrians are located at vertices
`3986`

,`9411`

. - All pedestrians want to go to vertex
`13009`

. - 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[3986, 9411], 13009,
directed := false);
```

Walking back to the hotels after having the beer (in seconds).

- All pedestrians are starting from vertex
`13009`

. - Pedestrians want to go to locations
`3986`

,`9411`

. - 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',
13009, ARRAY[3986, 9411],
directed := false);
```

Walking from the hotels to the Market and to the Aquarium (in minutes).

- The hotels are located at vertices
`3986`

,`9411`

. - Pedestrians want to go to destinations
`8401`

,`12235`

. - The cost to be in minutes, 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 / 60 AS cost
FROM ways',
ARRAY[3986, 9411],
ARRAY[8401, 12235],
directed := false);
```

Note

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

- Going to vertex 8401:
- from 3986 takes 23.4190755088423 minutes (row 42)
- from 9411 takes 26.7078952983972 minutes (row 125)

- Going to to vertex 12235:
- from 3986 takes 23.9778917105248 minutes (row 83)
- from 9411 takes 26.7679707128945 minutes (row 167)

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 hotels to the Market and to the Aquarium (get only the cost in minutes).

- The hotels are located at vertices
`3986`

,`9411`

. - Pedestrians want to go to destinations
`8401`

,`12235`

. - 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[3986, 9411],
ARRAY[8401, 12235],
directed := false);
```

Compare with Exercise 4 ‘s note.

Walking from the hotels to the Market and to the Aquarium (sumirize cost in minutes).

- The hotels are located at vertices
`3986`

,`9411`

. - Pedestrians want to go to destinations
`8401`

,`12235`

. - 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[3986, 9411],
ARRAY[8401, 12235],
directed := false)
GROUP BY end_vid
ORDER BY end_vid;
```

Note

An interpretation of the result can be: In general, it is slightly faster to go to the Aquarium from any of the hotels.