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);
