 # pgr_dijkstra - Shortest Path Dijkstra¶

## Name¶

pgr_dijkstra — Returns the shortest path using Dijkstra algorithm.

## Synopsis¶

Dijkstra’s algorithm, conceived by Dutch computer scientist Edsger Dijkstra in 1956. It is a graph search algorithm that solves the single-source shortest path problem for a graph with non-negative edge path costs, producing a shortest path tree. Returns a set of pgr_costResult (seq, id1, id2, cost) rows, that make up a path.

```pgr_costResult[] pgr_dijkstra(text sql, integer source, integer target,
boolean directed, boolean has_rcost);
```

## Description¶

sql:

a SQL query, which should return a set of rows with the following columns:

```SELECT id, source, target, cost [,reverse_cost] FROM edge_table
```
id: int4 identifier of the edge int4 identifier of the source vertex int4 identifier of the target vertex float8 value, of the edge traversal cost. A negative cost will prevent the edge from being inserted in the graph. float8 (optional) the cost for the reverse traversal of the edge. This is only used when the directed and has_rcost parameters are true (see the above remark about negative costs).
source:

int4 id of the start point

target:

int4 id of the end point

directed:

true if the graph is directed

has_rcost:

if true, the reverse_cost column of the SQL generated set of rows will be used for the cost of the traversal of the edge in the opposite direction.

Returns set of pgr_costResult[]:

seq: row sequence node ID edge ID (-1 for the last row) cost to traverse from id1 using id2

History

• Renamed in version 2.0.0

## Examples¶

• Without reverse_cost
```SELECT seq, id1 AS node, id2 AS edge, cost
FROM pgr_dijkstra(
'SELECT id, source, target, cost FROM edge_table',
7, 12, false, false
);

seq | node | edge | cost
-----+------+------+------
0 |    7 |    8 |    1
1 |    8 |    9 |    1
2 |    9 |   15 |    1
3 |   12 |   -1 |    0
(4 rows)
```
• With reverse_cost
```SELECT seq, id1 AS node, id2 AS edge, cost
FROM pgr_dijkstra(
'SELECT id, source, target, cost, reverse_cost FROM edge_table',
7, 12, true, true
);

seq | node | edge | cost
-----+------+------+------
0 |    7 |    8 |    1
1 |    8 |    9 |    1
2 |    9 |   15 |    1
3 |   12 |   -1 |    0
(4 rows)
```

The queries use the Sample Data network.