pgRouting Manual (2.0.0)

pgr_kDijkstra - Plus court chemin Dijkstra à multiples destinations

«  pgr_dijkstra - Plus court chemin Dijkstra   ::   Contenu   ::   pgr_ksp - K-plus court chemin  »

pgr_kDijkstra - Plus court chemin Dijkstra à multiples destinations

Nom

  • pgr_kdijkstraCost - Retourne les coûts pour les K plus courts chemins utilisant l’algoithme Dijkstra.
  • pgr_kdijkstraPath - Retourne les chemins pour les K plus courts chemins en utilisant l’algorithme Dijkstra.

Synopsis

Ces fonctions vous autorisent à avoir un unique nœud de départ et des nœuds de destination multiple et va calculer les routes pour toutes les destinations depuis le noeud source. Retourne un ensemble de pgr_costResult3 ou pgr_costResult3. pgr_kdijkstraCost Retourne un enregistrement pour chaque nœud et le coût est le coût total de la route vers ce noeud. pgr_kdijkstraPath retourne un enregistrement pour chaque nœud dans ce chemin depuis la source vers la destination et le coût pour traverser cette arête.

pgr_costResult[] pgr_kdijkstraCost(text sql, integer source,
                 integer[] targets, boolean directed, boolean has_rcost);

pgr_costResult3[] pgr_kdijkstraPath(text sql, integer source,
                  integer[] targets, boolean directed, boolean has_rcost);

Description

sql:

une requête SQL, qui devrait retourner un ensemble de lignes avec les colonnes suivantes :

SELECT id, source, target, cost [,reverse_cost] FROM edge_table
id:int4 identifiant de l’arête
source:int4 identifiant du sommet source
target:int4 identifiant du sommet cible
cost:float8 valeur, du coût de l’arête traversée. Un coût négatif va prévenir l’arête d’être insérée dans le graphe.
reverse_cost:(optionnel) le coût pour la traversée inverse de l’arête. Ceci est seulement utilisé quand les paramètres directed et has_rcost sont true (voir la remarque ci-dessus sur les coûts négatifs).
source:

int4 id du point de départ

targets:

int4[] un tableau d’ids des points finaux

directed:

true si le graphe est dirigé

has_rcost:

si true, la colonne reverse_cost du SQL générant l’ensemble des lignes va être utilisé pour le coût de la traversée de l’arête dans la direction opposée.

pgr_kdijkstraCost retourne un ensemble de pgr_costResult[]:

seq:séquence de ligne
id1:id source du chemin de sommets (cela va toujours être la source du point final dans la requête).
id2:id cible du sommet du chemin
cost:coût pour traverser le chemin de id1 à id2. Le coût sera de -1.0 si il n’y a pas de chemin pour cet id de sommet cible.

pgr_kdijkstraPath retourne un ensemble de pgr_costResult3[] - Résultats du chemin multiple avec coût:

seq:séquence de ligne
id1:id chemin cible (identifie le chemin cible).
id2:path edge source node id
id3:path edge id (-1 for the last row)
cost:coût pour traverser l’arête ou -1.0 si il n’y a pas de chemin pour cette cible

Histoire

  • Nouveau depuis la version 2.0.0

Exemples

  • Retourne un résultat cost
SELECT seq, id1 AS source, id2 AS target, cost FROM pgr_kdijkstraCost(
    'SELECT id, source, target, cost FROM edge_table',
    10, array[4,12], false, false
);

 seq | source | target | cost
-----+--------+--------+------
   0 |     10 |      4 |    4
   1 |     10 |     12 |    2
SELECT seq, id1 AS path, id2 AS node, id3 AS edge, cost
  FROM pgr_kdijkstraPath(
      'SELECT id, source, target, cost FROM edge_table',
      10, array[4,12], false, false
);

 seq | path | node | edge | cost
-----+------+------+------+------
   0 |    4 |   10 |   12 |    1
   1 |    4 |   11 |   13 |    1
   2 |    4 |   12 |   15 |    1
   3 |    4 |    9 |   16 |    1
   4 |    4 |    4 |   -1 |    0
   5 |   12 |   10 |   12 |    1
   6 |   12 |   11 |   13 |    1
   7 |   12 |   12 |   -1 |    0
(8 rows)
  • Retourne un résultat
SELECT id1 as path, st_astext(st_linemerge(st_union(b.the_geom))) as the_geom
  FROM pgr_kdijkstraPath(
                  'SELECT id, source, target, cost FROM edge_table',
                  10, array[4,12], false, false
            ) a,
            edge_table b
WHERE a.id3=b.id
GROUP by id1
ORDER by id1;

path |            the_geom
------+---------------------------------
    4 | LINESTRING(2 3,3 3,4 3,4 2,4 1)
   12 | LINESTRING(2 3,3 3,4 3)
(2 rows)

Il n’y a pas d’assurance que le résultat au-dessus sera ordonné dans la direction du flot de la route, càd : il peut être inversé. Vous aurez besoin de vérifier si st_startPoint() de la route est la même que la localisation du point de départ et si ça ne l’est pas, alors appelez st_reverse() pour inverser la direction de la route. Ce comportement est l’une des fonctions PostGIS st_linemerge() et st_union() et non pgRouting.

«  pgr_dijkstra - Plus court chemin Dijkstra   ::   Contenu   ::   pgr_ksp - K-plus court chemin  »