Les deux algorithmes Dijkstra et A* permettent de calculer le coût pour chaque orientation de l'arc d'un graphe, ce qui peut être très utile lors de la recherche de chemins avec un réseau routier qui a des rues en sens uniques.
Ce petit exemple illustrera comment cela est fait. Les données utilisées dans cet exemple ont été créées en utilisant OpenJump et ont ensuite été charger dans une base de données PostGIS pour laquelle pgRouting à aussi été installlé.
Le graphe ressemble à ceci; remarquez que l'arc #2 à été arienté de droite à gauche, contrairement à la plupart des arcs qui ont été orienté de gauche à droite. Cela a été fait comme cela pour simuler une route à sens unique.
Lors du calcul pour le coût de chaque coté d'un arc, un champ représentant le coût inverse (rcoast) doit être passer en argument à l'olgorithme de routage.
Intiallement, les deux coût (coast,rcoast) ont la même valeur qui est la longueur de l'arc.
Ensuite, pour agmenter le coût inverse de l'arc n°2 , une valeur de 1000000 sera ajouter à la valeur de la colonne rcoast.
gid | cost | rcost | source | target ----+------------------+---------------------+--------+-------- 1 | 90.4777391240398 | 90.4777391240398 | 1 | 2 2 | 266.663211021467 | 000266.663211021467 | 3 | 2 3 | 74.7975644284963 | 74.7975644284963 | 2 | 4 4 | 264.887335603738 | 264.887335603738 | 4 | 5 5 | 49.0618009646755 | 49.0618009646755 | 3 | 5 (5 rows)
Le dernier argument passé aux algoithmes Dijkstra et A* détermine si le coût inverse doit aussi être calculé lors de la recherche d'un chemin à travers le graphe.
Lorsque vous lui attribué la valeur faux, les deux algorithmes effectueront la recherche en utilisant uniquement le paramètre coût, qui est simplement dans ce cas la longueur de chaque arc. Avec notre exemple, nous trouverons un chemin partant du noeud n°1 jusqu'au noeud n°3.
routing=# select *
from shortest_path_astar(
'select gid as id,
source::int4,
target::int4,
cost::double precision,
rcost::double precision as reverse_cost,
x1,y1,x2,y2
from rtest',
1,3,false,false);
vertex_id | edge_id | cost
-----------+---------+------------------
1 | 1 | 90.4777391240398
2 | 2 | 266.663211021467
3 | -1 | 0
(3 rows)
Maintenant, si nous attribuons la valeur vrai au paramètre inverse, les algorithmes utilseront alors le coût inverse, ils constateront que le noeud 2 de l'arc n°2 a un coup très élevé et chercheront donc un autre chemin.
routing=# select *
from shortest_path_astar(
'select gid as id,
source::int4,
target::int4,
cost::double precision,
rcost::double precision as reverse_cost,
x1,y1,x2,y2
from rtest',
1,3,false,true);
vertex_id | edge_id | cost
----------+---------+------------------
1 | 1 | 90.4777391240398
2 | 3 | 74.7975644284963
4 | 4 | 264.887335603738
5 | 5 | 49.0618009646755
3 | -1 | 0
(5 rows)
Bien que nous ayons la possibilité de calculer le coût de chaque sens de l'arc, c'est très astucieux, cela reste néanmoins très couteux puisqu'il influera fortement sur les performances et devrait donc être utilisé seulement lorsque c'est vraiment nécessaire.
routing=# explain analyze
from shortest_path_astar(
'select gid as id,
source::int4,
target::int4,
cost::double precision,
rcost::double precision as reverse_cost,
x1,y1,x2,y2
from rtest',
1,3,false,false);
QUERY PLAN
--------------------------------------------------------------------------------
Function Scan on shortest_path_astar (cost=0.00..12.50 rows=1000 width=16)
(actual time=0.954..0.958 rows=3 loops=1) Total runtime: 1.020 ms
(2 rows)
routing=# explain analyze
from shortest_path_astar(
'select gid as id,
source::int4,
target::int4,
cost::double precision,
rcost::double precision as reverse_cost,
x1,y1,x2,y2
from rtest',
1,3,false,false);
QUERY PLAN
--------------------------------------------------------------------------------
Function Scan on shortest_path_astar (cost=0.00..12.50 rows=1000 width=16)
(actual time=11.088..11.093 rows=5 loops=1) Total runtime: 11.155 ms
(2 rows)