{"id":3292,"date":"2016-06-01T13:59:09","date_gmt":"2016-06-01T12:59:09","guid":{"rendered":"http:\/\/www.sigterritoires.fr\/?p=3292"},"modified":"2016-06-01T13:59:09","modified_gmt":"2016-06-01T12:59:09","slug":"developper-une-application-avec-pgrouting-sous-windows-3lalgorithme-dijkstra","status":"publish","type":"post","link":"https:\/\/www.sigterritoires.fr\/index.php\/developper-une-application-avec-pgrouting-sous-windows-3lalgorithme-dijkstra\/","title":{"rendered":"D\u00e9velopper une application avec pgrouting sous Windows (3):l\u2019algorithme Dijkstra"},"content":{"rendered":"

L’algorithme de Dijkstra prend en entr\u00e9e un graphe orient\u00e9 pond\u00e9r\u00e9 par des r\u00e9els positifs et un sommet source. Il s’agit de construire progressivement un sous-graphe dans lequel sont class\u00e9s les diff\u00e9rents sommets par ordre croissant de leur distance minimale au sommet de d\u00e9part. La distance correspond \u00e0 la somme des poids des arcs emprunt\u00e9es.<\/p>\n

La syntaxe de l\u2019algorithme Dijkstra est la suivante:<\/p>\n

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

O\u00f9 source<\/strong> <\/em>est le point de d\u00e9part souhait\u00e9 de l\u2019itin\u00e9raire, target<\/strong> <\/em>le point d\u2019arriv\u00e9e de l\u2019itin\u00e9raire et la cha\u00eene sql est de type:<\/p>\n

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

La variable bool\u00e9enne \u00ab\u00a0directed\u00a0\u00bb permet la prise en compte des voies \u00e0 sens unique. Par d\u00e9faut elle est \u00ab\u00a0true\u00a0\u00bb.<\/p>\n

La commande retourne un ensemble d’\u00e9l\u00e9ments (seq, path_seq [, start_vid] [, end_vid], node, edge<\/a>, cost, agg_cost). Contrairement \u00e0 l’algorithme A*, o\u00f9 on a un point de d\u00e9part et un points d’arriv\u00e9e pour l’itin\u00e9raire, l’algorithme de Dijstra admet plusieurs points d’entr\u00e9e et de sortie.<\/p>\n

Dans l’ensemble de sortie, seq<\/strong> <\/em>est le num\u00e9ro d’ordre du segment dans l’ensemble global, path_seq<\/strong><\/em> est le num\u00e9ro d’ordre du segment dans l’itin\u00e9raire, start_vid<\/strong><\/em> et end_vid<\/strong><\/em> correspondent au point de d\u00e9part et d’arriv\u00e9e de l’itin\u00e9raire et ne sont renseign\u00e9s que s’il y a plusieurs source<\/strong><\/em> ou target<\/strong> <\/em>en param\u00e8tre de l’algorithme, node<\/strong> <\/em>et edge<\/strong> <\/em>sont les points de d\u00e9but et fin du tron\u00e7on consid\u00e9r\u00e9, cost<\/strong> <\/em>est le co\u00fbt du tron\u00e7on et agg_cost<\/strong><\/em> est le co\u00fbt cumul\u00e9 depuis le d\u00e9part de l’itin\u00e9raire.<\/p>\n

Choix du \u201cco\u00fbt\u201d d\u2019un tron\u00e7on.<\/h2>\n
L\u2019algorithme de routage recherche le chemin avec le co\u00fbt le plus faible. En fonction de vos objectifs, vous devez d\u00e9cider quel \u00e9l\u00e9ment de co\u00fbt vous allez prendre en charge.<\/p>\n
Reprenons notre base OpensStreetMap. Vous avez un champ \u201ccost\u201d qui reprend la longueur du tron\u00e7on en degr\u00e9s. Si vous utilisez ce champ dans l\u2019algorithme Dijkstra comme valeur de co\u00fbt, l\u2019itin\u00e9raire propos\u00e9 sera le plus court chemin entre les deux points choisis. Voyons un exemple.<\/p>\n
La commande suivante calcule l\u2019itin\u00e9raire entre les points 69072 et 64204 en utilisant le champ \u201ccost\u201d qui correspond \u00e0 la longueur du tron\u00e7on.<\/p>\n
SELECT seq, path_seq, node,\u00a0 edge,di.cost, agg_cost, the_geom
\nFROM pgr_dijkstra(
\n‘SELECT gid as id, source, target, cost, reverse_cost FROM public.ways’,
\n69072, 64204, false\u00a0 ) as di
\nJOIN public.ways ways_vertices_pgr
\nON di.edge = ways_vertices_pgr.gid ;<\/p>\n
$\"4pg3\"$ <\/a><\/p>\n
Le r\u00e9sultat, une fois charg\u00e9 dans QGis est le m\u00eame que pour l’algorithme A<\/p>\n
$\"r\u00e9sultat$ <\/a>Probl\u00e8mes<\/h2>\n
Par rapport \u00e0 l’algorithme A, vous remarquerez qu’il y a moins besoin de mise en forme de la table de la couche r\u00e9seau. Par contre, si vous utilisez les champs cost_s et reverse_cost_s, vous aurez les m\u00eames messages d’erreur s’il y a des valeurs nulles. Reportez vous \u00e0 l’article pr\u00e9c\u00e9dent (D\u00e9velopper une application avec pgrouting sous Windows (2):l\u2019algorithme A<\/a>) pour r\u00e9soudre ces probl\u00e8mes.<\/p>\n
Pour cet article nous utilisons la version 2.2.3 de pgrouting<\/a>. Si vous utilisez des versions ant\u00e9rieures vous pouvez rencontrer un probl\u00e8me de type de champ source<\/strong> <\/em>et target<\/strong> <\/em>de votre base de donn\u00e9es:<\/p>\n
$\"erreur$ <\/a>En effet, si le nombre de n\u0153uds de votre r\u00e9seau est trop important, les champs source<\/strong> <\/em>et target<\/strong> <\/em>peuvent \u00eatre de type bigint. Les versions ant\u00e9rieures de pgrouting ne prenaient pas en compte ce type d’entier.<\/p>\n
V\u00e9rifiez votre version avec la requ\u00eate SQL<\/p>\n
SELECT pgr_version();<\/strong><\/p>\n
Itin\u00e9raires multiples<\/h2>\n
Voici un exemple de calcul d’itin\u00e9raire avec trois points de d\u00e9part et un points d’arriv\u00e9e:<\/p>\n
SELECT seq, path_seq, start_vid, node,\u00a0 edge,di.cost, agg_cost, the_geom
\nFROM pgr_dijkstra(
\n‘SELECT gid as id, source, target, cost_s as cost, reverse_cost_s as reverse_cost FROM public.ways’,
\nARRAY[69072,21576,62667]<\/strong>, 64204, true\u00a0 ) as di
\nJOIN public.ways ways_vertices_pgr
\nON di.edge = ways_vertices_pgr.gid ;<\/p>\n
Cette requ\u00eate calcule les itin\u00e9raires entre les points de d\u00e9part\u00a069072, 21576 et 62667 et le point d’arriv\u00e9e 64204<\/p>\n
$\"requ\u00eate$ <\/a>Le r\u00e9sultat, une fois charg\u00e9 dans QGis est le suivant<\/p>\n
$\"r\u00e9sultat$ <\/a><\/p>\n
Variante pgr_dijkstraCost<\/h2>\n
Vous disposez d’une variante de l’algorithme Dijkstra avec laquelle vous donnez le point de d\u00e9part et le point d’arriv\u00e9e et en retour vous r\u00e9cup\u00e9rez simplement le co\u00fbt total du trajet.<\/p>\n
Voici un exemple avec le trajet entre les points 69072 et 64204<\/p>\n
SELECT FROM pgr_dijkstraCost(
\n‘SELECT gid as id, source, target, cost_s as cost, reverse_cost_s as reverse_cost FROM public.ways’,
\n69072, 64204) ;<\/p>\n
$\"exemple$ <\/a><\/p>\n","protected":false},"excerpt":{"rendered":"
L’algorithme de Dijkstra prend en entr\u00e9e un graphe orient\u00e9 pond\u00e9r\u00e9 par des r\u00e9els positifs et un sommet source. Il s’agit de construire progressivement un sous-graphe dans lequel sont class\u00e9s les diff\u00e9rents sommets par ordre croissant de…<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"give_campaign_id":0,"_bbp_topic_count":0,"_bbp_reply_count":0,"_bbp_total_topic_count":0,"_bbp_total_reply_count":0,"_bbp_voice_count":0,"_bbp_anonymous_reply_count":0,"_bbp_topic_count_hidden":0,"_bbp_reply_count_hidden":0,"_bbp_forum_subforum_count":0,"sfsi_plus_gutenberg_text_before_share":"","sfsi_plus_gutenberg_show_text_before_share":"","sfsi_plus_gutenberg_icon_type":"","sfsi_plus_gutenberg_icon_alignemt":"","sfsi_plus_gutenburg_max_per_row":"","_monsterinsights_skip_tracking":false,"_monsterinsights_sitenote_active":false,"_monsterinsights_sitenote_note":"","_monsterinsights_sitenote_category":0,"jetpack_post_was_ever_published":false,"_jetpack_newsletter_access":"","_jetpack_dont_email_post_to_subs":false,"_jetpack_newsletter_tier_id":0,"_jetpack_memberships_contains_paywalled_content":false,"_jetpack_memberships_contains_paid_content":false,"footnotes":""},"categories":[311,62],"tags":[331,330,327,326,227,312,58],"class_list":["post-3292","post","type-post","status-publish","format-standard","hentry","category-postgresql","category-qgis-2","tag-algorithme","tag-dijkstra","tag-itineraire","tag-pgrouting","tag-postgis","tag-postgresql","tag-qgis"],"aioseo_notices":[],"jetpack_featured_media_url":"","jetpack_shortlink":"https:\/\/wp.me\/p6XU0A-R6","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/www.sigterritoires.fr\/index.php\/wp-json\/wp\/v2\/posts\/3292","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.sigterritoires.fr\/index.php\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.sigterritoires.fr\/index.php\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.sigterritoires.fr\/index.php\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.sigterritoires.fr\/index.php\/wp-json\/wp\/v2\/comments?post=3292"}],"version-history":[{"count":0,"href":"https:\/\/www.sigterritoires.fr\/index.php\/wp-json\/wp\/v2\/posts\/3292\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.sigterritoires.fr\/index.php\/wp-json\/wp\/v2\/media?parent=3292"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.sigterritoires.fr\/index.php\/wp-json\/wp\/v2\/categories?post=3292"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.sigterritoires.fr\/index.php\/wp-json\/wp\/v2\/tags?post=3292"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}