Given a graph and a source vertex in the

graph, Dijkstra’s

algorithm finds the shortest

paths from source to all vertices in the given graph. It takes as input an oriented graph weighted by real positive

numbers and a top source as root. This is to build gradually a subgraph where

the different vertices are classified in ascending order according their

minimum distance from the root. The distance is the sum of the weights of the

arcs followed.

The syntax of the Dijkstra algorithm is as follows :

**pgr_dijkstrar** **(** **sql** text **, source** integer **,
target** integer

**, directed**boolean

**);**

Where ** source** is the desired starting point desired,

*target*is the end point of the route and the chain sql is as follows:

**SELECT id, source, target, cost [,** **reverse_cost** **] FROM**

**network**

The “directed” Boolean variable allows taking into account of one-way

route. By default it is ” true

“.

The order returns a set of elements ( seq , path_seq [, start_vid ] [,

end_vid ], node, edge, cost, agg_cost ). Unlike the A * algorithm, which has a

starting point and an end point for the route, the Dijstra algorithm admits several

points of entry and exit.

In the output set, ** seq** is the order number of the segment

in the global set ,

**is the order number of the segment**

*path_seq*in the route ,

**and**

*start_vid***are the point**

*end_vid*of departure and arrival of the route and are not informed unless there are

several

**or**

*sources***in parameter of the**

*targets*algorithm ,

**and**

*node***are the start and end**

*edge*points of the section considered ,

**is the cost of the sectionand**

*cost***is the cost accrued since the departure of the route .**

*agg_cost***Choice** **of the “cost** **” of a** **section** **.**

The shortest path algorithm searches the path with the lowest cost. According

to your goals , it is up to you to decide which cost element you going take into

account.

Let’s take back our OpensStreetMap database . You have a “cost”

field that considers the length of the section in degrees . If you use this

field in the Dijkstra algorithm as cost value, the proposed route will be the

shortest path between the two selected points . Let’s see an example .

The following order calculates the route between the points 69072 and

64204 by using the “cost” field which corresponds to the length of

the section .

SELECT seq , path_seq , node, edge,

di.cost , agg_cost , the_geom

FROM pgr_dijkstra (

‘SELECT gid as id, source, target, cost, reverse_cost FROM public.ways ‘,

69072, 64204, false ) as di

JOIN public.ways ways_vertices_pgr

ON di.edge = ways_vertices_pgr.gid ;

Once

loaded in QGis, the result is the same as for algorithm A *

**Problems**

When comparing this algorithm with the algorithm A *, you will notice that

there is less need to formatting the layer network . By cons, if you use the cost_s

and reverse_cost_s fields , you will obtain the same error messages as if there

were null values . Refer to a previous article ( Developping an application with pgrouting in Windows (2): the algorithm

A * ) to solve these problems .

For this article we use pgrouting version 2.2.3. If you use earlier versions you

can encounter a ** source** and

**field type problem of your**

*target*database:

Indeed , if the number of nodes in your network is high, the *source*

and ** target** fields can be bigint type . Earlier pgRouting versions

did not take into account this type of integer .

Check your version with the SQL query

**SELECT** **pgr_version** **();**

**Multiple** **routes**

Here is an example of a path calculation with three starting points and

one arrival point :

SELECT seq , path_seq , start_vid , node, edge, di.cost ,

agg_cost , the_geom

FROM pgr_dijkstra (

‘SELECT gid as id, source, target, cost_s as cost, reverse_cost_s as

reverse_cost FROM public.ways ‘,

**ARRAY [69072,21576,62667]** , 64204, true ) as di

JOIN public.ways ways_vertices_pgr

ON di.edge = ways_vertices_pgr.gid ;

This request calculates the paths between the

starting points 69072, 21576 and 62667 and the point of arrival 64204

Once

QGis is loaded, the result is the following

**Variant** **pgr_dijkstraCost**

You have a Dijkstra algorithm variant with which you state the starting and

arrival point and in return you retrieve the total cost of the path.

Here is an example with the path between points 69072 and 64204

SELECT * FROM pgr_dijkstraCost (

‘SELECT gid as id, source, target, cost_s as cost, reverse_cost_s as

reverse_cost FROM public.ways ‘,

69072, 64204);