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 , path_seq is the order number of the segment
in the route , start_vid and end_vid are the point
of departure and arrival of the route and are not informed unless there are
several sources or targets in parameter of the
algorithm , node and edge are the start and end
points of the section considered , cost is the cost of the sectionand
agg_cost is the cost accrued since the departure of the route .
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 target field type problem of your
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);
