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
|
||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|
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.