pgr_dijkstra - Plus court chemin Dijkstra¶

Nom¶

pgr_dijkstra — Retourne le plus court chemin en utilisant l’algorithme Dijkstra.

Synopsis¶

L’algorithme Dijkstra, conçu par l’informaticien Néerlandais Edsger Dijkstra en 1956. C’est un algorithme de recherche de graphe qui résout le problème de plus court chemin à source unique pour un graphe à coûts de chemin non négatifs, produisant un arbre de plus court chemin. Retourne un ensemble de lignes pgr_costResult (seq, id1, id2, cost) rows, qui fabriquent un chemin.

pgr_costResult[] pgr_dijkstra(text sql, integer source, integer target,
                           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:	`float8` (optional) the cost for the reverse traversal of the edge. This is only used when the `directed` and `has_rcost` parameters are `true` (see the above remark about negative costs).

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 à partir de `id1` en utilisant `id2`

Histoire

Renommé depuis la version 2.0.0

Exemples¶

Sans reverse_cost

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

 seq | node | edge | cost
-----+------+------+------
   0 |    7 |    8 |    1
   1 |    8 |    9 |    1
   2 |    9 |   15 |    1
   3 |   12 |   -1 |    0
(4 rows)

Avec reverse_cost

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

 seq | node | edge | cost
-----+------+------+------
   0 |    7 |    8 |    1
   1 |    8 |    9 |    1
   2 |    9 |   15 |    1
   3 |   12 |   -1 |    0
(4 rows)

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

pgRouting Manual (2.0.0)