{"id":7870,"date":"2019-01-22T05:30:21","date_gmt":"2019-01-22T04:30:21","guid":{"rendered":"http:\/\/www.sigterritoires.fr\/?p=7870"},"modified":"2019-01-22T17:32:07","modified_gmt":"2019-01-22T16:32:07","slug":"developing-and-application-with-pgrouting-in-windows-3-the-dijkstra-algorithm","status":"publish","type":"post","link":"https:\/\/www.sigterritoires.fr\/index.php\/en\/developing-and-application-with-pgrouting-in-windows-3-the-dijkstra-algorithm\/","title":{"rendered":"How to develop an application with pgrouting in Windows (3): the Dijkstra algorithm"},"content":{"rendered":"\n

Given a graph and a source vertex in the\ngraph, Dijkstra’s\nalgorithm finds the shortest\npaths from source to all vertices in the given graph. It takes as input an oriented graph weighted by real positive\nnumbers and a top source as root. This is to build gradually a subgraph where\nthe different vertices are classified in ascending order according their\nminimum distance from the root. The distance is the sum of the weights of the\narcs followed. <\/p>\n\n\n\n

The syntax of the Dijkstra algorithm is as follows : <\/p>\n\n\n\n\n\n\n\n

pgr_dijkstrar<\/strong> (<\/strong> sql<\/strong> text , source<\/strong> integer ,\ntarget<\/strong> integer , directed<\/strong> boolean );<\/strong> <\/p>\n\n\n\n

Where source<\/em><\/strong> is the desired starting point desired, target<\/em><\/strong>\nis the end point of the route and the chain sql is as follows: <\/p>\n\n\n\n

SELECT id, source, target, cost [,<\/strong> reverse_cost<\/strong> ] FROM<\/strong>\nnetwork<\/strong> <\/p>\n\n\n\n

The \u201cdirected\u201d Boolean variable allows taking into account of one-way\nroute. By default it is \u00a0\u00bb true\n \u00ab\u00a0. <\/p>\n\n\n\n

The order returns a set of elements ( seq , path_seq [, start_vid ] [,\nend_vid ], node, edge, cost, agg_cost ). Unlike the A * algorithm, which has a\nstarting point and an end point for the route, the Dijstra algorithm admits several\npoints of entry and exit. <\/p>\n\n\n\n

In the output set, seq<\/em><\/strong> is the order number of the segment\nin the global set , path_seq<\/em><\/strong> is the order number of the segment\nin the route , start_vid<\/em><\/strong> and end_vid<\/em><\/strong> are the point\nof departure and arrival of the route and are not informed unless there are\nseveral sources<\/em><\/strong> or targets<\/em><\/strong> in parameter of the\nalgorithm , node<\/em><\/strong> and edge<\/em><\/strong> are the start and end\npoints of the section considered , cost<\/em><\/strong> is the cost of the sectionand\nagg_cost<\/em><\/strong> is the cost accrued since the departure of the route . <\/p>\n\n\n\n

Choice<\/strong> of the \u00ab\u00a0cost<\/strong> \u00a0\u00bb of a<\/strong> section<\/strong> .<\/strong> <\/p>\n\n\n\n

The shortest path<\/a> algorithm searches the path with the lowest cost. According\nto your goals , it is up to you to decide which cost element you going take into\naccount. <\/p>\n\n\n\n

Let\u2019s take back our OpensStreetMap database . You have a \u00ab\u00a0cost\u00a0\u00bb\nfield that considers the length of the section in degrees . If you use this\nfield in the Dijkstra algorithm as cost value, the proposed route will be the\nshortest path between the two selected points . Let’s see an example . <\/p>\n\n\n\n

The following order calculates the route between the points 69072 and\n64204 by using the \u00ab\u00a0cost\u00a0\u00bb field which corresponds to the length of\nthe section . \n\nSELECT seq , path_seq , node, edge,\ndi.cost , agg_cost , the_geom
\nFROM pgr_dijkstra (
\n‘SELECT gid as id, source, target, cost, reverse_cost FROM public.ways ‘,
\n69072, 64204, false ) as di
\nJOIN public.ways ways_vertices_pgr
\nON di.edge = ways_vertices_pgr.gid ; \n\n\n\n<\/p>\n\n\n\n