Développer une application avec pgrouting sous Windows (3):l’algorithme Dijkstra

L’algorithme de Dijkstra prend en entrée un graphe orienté pondéré par des réels positifs et un sommet source. Il s’agit de construire progressivement un sous-graphe dans lequel sont classés les différents sommets par ordre croissant de leur distance minimale au sommet de départ. La distance correspond à la somme des poids des arcs empruntées.

La syntaxe de l’algorithme Dijkstra est la suivante:

pgr_dijkstrar(sql text, source integer, target integer,directed boolean);

source est le point de départ souhaité de l’itinéraire, target le point d’arrivée de l’itinéraire et la chaîne sql est de type:

SELECT id, source, target, cost [,reverse_cost] FROM réseau

La variable booléenne « directed » permet la prise en compte des voies à sens unique. Par défaut elle est « true ».

La commande retourne un ensemble d’éléments (seq, path_seq [, start_vid] [, end_vid], node, edge, cost, agg_cost). Contrairement à l’algorithme A*, où on a un point de départ et un points d’arrivée pour l’itinéraire, l’algorithme de Dijstra admet plusieurs points d’entrée et de sortie.

Dans l’ensemble de sortie, seq est le numéro d’ordre du segment dans l’ensemble global, path_seq est le numéro d’ordre du segment dans l’itinéraire, start_vid et end_vid correspondent au point de départ et d’arrivée de l’itinéraire et ne sont renseignés que s’il y a plusieurs source ou target en paramètre de l’algorithme, node et edge sont les points de début et fin du tronçon considéré, cost est le coût du tronçon et agg_cost est le coût cumulé depuis le départ de l’itinéraire.

Choix du “coût” d’un tronçon.

L’algorithme de routage recherche le chemin avec le coût le plus faible. En fonction de vos objectifs, vous devez décider quel élément de coût vous allez prendre en charge.

Reprenons notre base OpensStreetMap. Vous avez un champ “cost” qui reprend la longueur du tronçon en degrés. Si vous utilisez ce champ dans l’algorithme Dijkstra comme valeur de coût, l’itinéraire proposé sera le plus court chemin entre les deux points choisis. Voyons un exemple.

La commande suivante calcule l’itinéraire entre les points 69072 et 64204 en utilisant le champ “cost” qui correspond à la longueur du tronçon.

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 ;

4pg3

Le résultat, une fois chargé dans QGis est le même que pour l’algorithme A*

résultat dans QGis de l'algorithme de DijkstraProblèmes

Par rapport à l’algorithme A*, vous remarquerez qu’il y a moins besoin de mise en forme de la table de la couche réseau. Par contre, si vous utilisez les champs cost_s et reverse_cost_s, vous aurez les mêmes messages d’erreur s’il y a des valeurs nulles. Reportez vous à l’article précédent (Développer une application avec pgrouting sous Windows (2):l’algorithme A*) pour résoudre ces problèmes.

Pour cet article nous utilisons la version 2.2.3 de pgrouting. Si vous utilisez des versions antérieures vous pouvez rencontrer un problème de type de champ source et target de votre base de données:

erreur des versions antérieures de pgroutingEn effet, si le nombre de nœuds de votre réseau est trop important, les champs source et target peuvent être de type bigint. Les versions antérieures de pgrouting ne prenaient pas en compte ce type d’entier.

Vérifiez votre version avec la requête SQL

SELECT pgr_version();

Itinéraires multiples

Voici un exemple de calcul d’itinéraire avec trois points de départ et un points d’arrivée:

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 ;

Cette requête calcule les itinéraires entre les points de départ 69072, 21576 et 62667 et le point d’arrivée 64204

requête avec points de départ multiplesLe résultat, une fois chargé dans QGis est le suivant

résultat dans QGis du calcul d'itinéraires multiples

Variante pgr_dijkstraCost

Vous disposez d’une variante de l’algorithme Dijkstra avec laquelle vous donnez le point de départ et le point d’arrivée et en retour vous récupérez simplement le coût total du trajet.

Voici un exemple avec le trajet entre les points 69072 et 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) ;

exemple de pgr_dijkstraCost

16 pensées sur “Développer une application avec pgrouting sous Windows (3):l’algorithme Dijkstra”

  1. Bonjour, j’essaie de suivre ce tutoriel afin de me former au pgrouting.
    Malheureusement je n’ai aucun résultat après l’exécuition de votre requête sur la recherche du chemin le plus court avec l’algorithme du pgr_dijkstra()

    SELECT seq, path_seq, node, edge,di.cost, agg_cost,geom
    FROM pgr_dijkstra(
    ‘SELECT zid as id , source, target, longueur as cost FROM public.zem’,
    69072, 64204, false ) as di
    JOIN public.zem zem_vertices_pgr
    ON di.edge = zem_vertices_pgr.zid ;

    Je n’ai pas d’erreur sql mais juste un afficahge vide.
    j’utilise postgresql 9.5 avec le pgrouting 2.4.1

    Avez vous une idée sur ce disfontionnement svp?
    Merci

    1. Si le résultat est vide c’est qu’il ne trouve pas d’itinéraire entre les deux points. Essayez deux points proches dont vous pouvez vous assurer qu’il y a bien une série de tronçons continus.

      1. Je viens de m’apercevoir que les numéros renseignés dans la requête correspondent aux OSM id des routes. quel champ correspond dans la table ways aux points du réseau? Merci

        1. Si vous avez créée la topologie avec pgrCreateTopology c’est le dernier paramètre de la requête (pgr_CreateTopology(table,précision,géométrie,identifiant)
          Si vous avez récupéré le tout (table tronçons et table vertices) en principe c’est le champ identifiant de la table (le premier)

          1. Merci à vous. Le projet sur le quel je travaille comporte une table de chemins et une autre table de noeuds. les noeuds correspondent aux intersections qui existent entre mes différentes chemins formant à chaque fosi un tronçon.
            Je voudras dans ce cas savoir la démarche à suivre pour le chemin le plus court entre un noeud A et un noeud B.
            Bien entendu , l’utilisation du (pgr_create topology ) ne m’est pas utile ici car je ne veux pas créer des nouveaux points source et target dont je dispose dans ma table Noeud.

            Merci de vos recommandations par avance
            Cordialment

          2. Désolé mais ça ne marchera pas. Une table de tronçons doit avoir une table de vertices créée avec createtopology pour que les algorithmes de pgrouting fonctionnent. Vous aurez deux tables de noeuds, mais seulement celle créée avec createtopology sera utilisée dans la recherche d’itinéraire.

  2. Bonjour, je voudrais savoir les idées que vous préconiser pour développer une application autonome de recherche du chemin le plus court. parce que dans ce post vous nous donnez juste les étapes de recherche du chemin le plus court mais pas vraiment les outils pour mettre en place une mini application complète qui prenne en compte les traitements.
    Merci pour vos éclairages

    1. La suite des 7 articles permet d’avoir une approche depuis la mise en place de la base de données jusqu’à la page html de l’application.
      Qu’est-ce que vous entendez par « traitements » qui ne seraient pas pris en compte?

  3. j’entends par traitement la création des points de départ et d’arrivée pour chaque tronçon, les vertices et par la fin la requête avec l’algorithme de dijkstra. tous ces traitements sont bien expliqués et détaillés dans le tutoriel bien entendu.
    Ma question est de savoir comment automatiser tous ces traitements à chaque fois q’on serait appelé à changer de réseau; (En clair si on devait rechercher le chemin le plus court dans différentes régions de france) Est ce qu’il faudrait à chaque fois refaire les mêmes manipulations pour chaque région.
    Merci

    1. Si vous avez plusieurs tables, chacune pour une région différente, il suffit de configurer dans geoserver une vue correspondante à chaque région, puis dans openlayers ajouter un paramètre indiquant la région. Vous utiliserez alors le même code openlayers, et le même wrapper dans postgresql (dans ls paramètres du wrapper il y a le nom de la table à utiliser)

  4. Au fait je n’ai pas plusieurs tables, j’ai juste une table de réseau qui change puisque dans mon stage je suis appelé à travailler à chaque fois sur des réseaux différents qui changent d’une région à une autre en fonction du projet.

    1. J’arrive pas à bien saisir, vous avez une table qui change selon la région, ça veut bien dire que vous aurez une table pour chaque région? Si non ça veut dire que vous ajouterez des tronçons au fur et à mesure selon les régions à une seule table. Dans le premier cas, c’est la solution antérieure qui s’applique, dans le deuxième, vous ne’aurez rien à faire, selon mettre à jour la table des tronçons et repasser la commande pgr_createtopology dessus.

  5. ok bien reçu. Au lieu de passer par une application web, peut on interfacer avec QT directement dans qgis sans passer par une application web. si oui quel serait la démarche ? Merci

    1. En principe on doit pouvoir le faire. Je n’ai jamais essayé avec QT. En tout cas avec Python c’est possible de développer un plugin qui le fasse. Par contre pour décrire la démarche il faudrait plusieurs heures…Et tout dépend de ce que vous voulez vraiment faire.

Laisser un commentaire

Votre adresse de messagerie ne sera pas publiée. Les champs obligatoires sont indiqués avec *