Plus court chemin avec l'algorithme Dijkstra (sans heuristique)

La fonction shortest_path est définie de la manière suivante :

CREATE OR REPLACE FUNCTION shortest_path(sql text, source_id integer, 
       target_id integer, directed boolean, has_reverse_cost boolean) 
    RETURNS SETOF path_result

Les arguments sont les suivants :

sql

une requête SQL qui doit renvoyer les champs suivants :

SELECT id, source, target, cost FROM edge_table;

id: l'identifiant entier (int4) de l'arc
source: un identifiant entier (int4) du noeud de départ
target: un identifiant entier (int4) du noeud d'arrivée
cost: le coût de la traversée d'un arc (float8, un coût négatif permet de s'assurer qu'on ne passera jamais par cette arc)
reverse_cost : (optionel) le coût de la traversée de l'arc en sens invers. Cela n'estutilisé que lorsque la fonction est appelé avec l'argument has_reverse_cost à vrai.

source_id

identifiant du noeud de départ.

target_id

identifiant du noeud d'arrivée.

directed

vrai si le graphe est orienté.

has_reverse_cost

vrai si la colonne reverse_cost doit être considérée lors de la recherche du plus court chemin, dans le cas où lma traversée de l'arc se fait en sens invers.

Cette fonction renvoit un ensemble de tuples. Il y a un tuple par arc traversé et un tuple supplémentaire à la fin contenant le noeud d'arrivée. Les colonnes de chaque lignes sont les suivants :

vertext_id : l'identifiant du noeud source de chaque arc. Il y a une ligne supplémentaire contenant l'identifiant du noeud d'arrivée,
edge_id : l'identifiant de l'arc traversé,
cost : le coût de la traversée de l'arc. Cette valeur vaut 0 pour la dernière ligne renvoyée. Donc le coût total du parcour peut être calculé en faisant la somme des valeurs de cette colonne.

Exemple :

SELECT * FROM shortest_path('SELECT gid AS id, source::int4, 
          target::int4, length::double precision AS cost,
    FROM dourol',3, 7, false, false);

 vertex_id | edge_id | cost 
-----------+---------+------------------------
         3 |       2 |    0.000763954363701041
         4 |      21 |    0.00150254971056274
         6 |       5 |    0.000417442425988342
         7 |      -1 |    0
(4 rows)

SELECT * FROM shortest_path('SELECT gid AS id, source::int4, 
         target::int4, length::double precision AS cost,length::double precision 
    AS reverse_cost FROM dourol', 3, 7, true, true);