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.

pgRouting Manual (2.0.0)