pgr_ksp - K-plus court chemin¶

Nom¶

pgr_ksp — Retourne les “K” plus courts chemins.

Synopsis¶

L’algorithme de routage de K plus court chemin basé sur l’algorithme de Yen. “K” est le nombre de plus courts chemins souhaités. Retourne un ensemble de lignes pgr_costResult3 (seq, id1, id2, id3, cost), qui fabriquent un chemin.

pgr_costResult3[] pgr_ksp(sql text, source integer, target integer,
                         paths integer, has_rcost boolean);

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 utilisé seulement quand le paramètre `has_rcost` est `true` (voir la remarque au-dessus sur les coûts négatifs).

source:

int4 id du point de départ

target:

int4 id du point final

paths:

int4 bombre de routes alternatives

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.

Retourne un ensemble de pgr_costResult[]:

seq:	sequence for ording the results
id1:	ID route
id2:	ID noeud
id3:	ID arête (`0` pour la dernière ligne)
cost:	coût pour traverser de `id2` en utilisant `id3`

Code de base KSP ici : http://code.google.com/p/k-shortest-paths/source.

Histoire

Nouveau depuis la version 2.0.0

Exemples¶

Sans reverse_cost

SELECT seq, id1 AS route, id2 AS node, id3 AS edge, cost
 FROM pgr_ksp(
   'SELECT id, source, target, cost FROM edge_table',
   7, 12, 2, false
 );

 seq | route | node | edge | cost
-----+-------+------+------+------
   0 |     0 |    7 |    6 |    1
   1 |     0 |    8 |    7 |    1
   2 |     0 |    5 |    8 |    1
   3 |     0 |    6 |   11 |    1
   4 |     0 |   11 |   13 |    1
   5 |     0 |   12 |    0 |    0
   6 |     1 |    7 |    6 |    1
   7 |     1 |    8 |    7 |    1
   8 |     1 |    5 |    8 |    1
   9 |     1 |    6 |    9 |    1
  10 |     1 |    9 |   15 |    1
  11 |     1 |   12 |    0 |    0
(12 rows)

Avec reverse_cost

SELECT seq, id1 AS route, id2 AS node, id3 AS edge, cost
 FROM pgr_ksp(
   'SELECT id, source, target, cost, reverse_cost FROM edge_table',
   7, 12, 2, true
 );

 seq | route | node | edge | cost
-----+-------+------+------+------
   0 |     0 |    7 |    6 |    1
   1 |     0 |    8 |    7 |    1
   2 |     0 |    5 |    8 |    1
   3 |     0 |    6 |   11 |    1
   4 |     0 |   11 |   13 |    1
   5 |     0 |   12 |    0 |    0
   6 |     1 |    7 |    6 |    1
   7 |     1 |    8 |    7 |    1
   8 |     1 |    5 |    8 |    1
   9 |     1 |    6 |    9 |    1
  10 |     1 |    9 |   15 |    1
  11 |     1 |   12 |    0 |    0
(12 rows)

Les requêtes utilisent le réseau Données d’échantillon.

pgRouting Manual (2.0.0)