pgr_bdDijkstra - Plus court chemin bidirectionnel Dijkstra¶

Nom¶

pgr_bdDijkstra - Retourne le plus court chemin en utilisant l’algorithme bidirectionnel Dijkstra.

Synopsis¶

C’est un algorithme de recherche bidirectionnel Dijkstra. Cela recherche depuis la source vers la destination et en même temps depuis la destination vers la source et se termine quand ces deux recherches se rencontrent au milieu. Retourne un ensemble de lignes pgr_costResult (seq, id1, id2, cost), qui fabriquent un chemin.

pgr_costResult[] pgr_bdDijkstra(sql text, source integer, target integer,
                                directed boolean, 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 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

target:

int4 id du point final

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.

Retourne un ensemble de pgr_costResult[]:

seq:	séquence de ligne
id1:	ID noeud
id2:	ID arête (`-1` pour la dernière ligne)
cost:	coût pour traverser depuis `id1` en utilisant `id2`

Histoire

Nouveau depuis la version 2.0.0

Exemples¶

Sans reverse_cost

SELECT seq, id1 AS node, id2 AS edge, cost
    FROM pgr_bdDijkstra(
        'SELECT id, source, target, cost FROM edge_table',
        4, 10, false, false
    );

     seq | node | edge | cost
    -----+------+------+------
       0 |    4 |    3 |    0
       1 |    3 |    5 |    1
       2 |    6 |   11 |    1
       3 |   11 |   12 |    0
       4 |   10 |   -1 |    0
    (5 rows)

Avec reverse_cost

SELECT seq, id1 AS node, id2 AS edge, cost
    FROM pgr_bdDijkstra(
        'SELECT id, source, target, cost, reverse_cost FROM edge_table',
        4, 10, true, true
    );

     seq | node | edge | cost
    -----+------+------+------
       0 |    4 |    3 |    1
       1 |    3 |    2 |    1
       2 |    2 |    4 |    1
       3 |    5 |   10 |    1
       4 |   10 |   -1 |    0
    (5 rows)

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

pgRouting Manual (2.0.0)