Database Reference
In-Depth Information
How to do it...
Nowthatthedataareloaded,wecanrunaquicktest.We'lluseasimplealgorithm
called Dijkstra to calculate theshortest path from node 5 to node 12.
Tip
Dijkstra'salgorithmisaneffectiveandsimpleroutingalgorithmthatrunsasearch
of all available paths from point A to point B in a network, also known as the
graph structure
. It is not the most efficient routing algorithm, but will always
find the best route. For more information on Dijkstra's algorithm, refer to Wiki-
pedia,whichhasagoodexplanationwithillustrations,at
http://en.wikipedia.org/
wiki/Dijkstra%27s_algorithm
. See especially
http://en.wikipedia.org/wiki/
AnimportantpointtonoteisthatthenodesinpgRoutingcreatedduringthetopology
creationprocessarecreatednon-deterministicallyforsomeversions.Thishasbeen
patchedinfutureversions;butforsomeversionsofpgRouting,thismeansthatyour
node numbers will not be the same as those we use here in the topic. View your
datainanapplicationtodeterminewhichnodestouseoruseaKNNsearchforthe
node nearest to a static geographic point. See
Chapter 11
,
Using Desktop Clients
,
Data - Advanced Recipes
,forapproachestofindingthenearestnodeautomatically.
Dijkstra is run as in the following code:
SELECT pgr_dijkstra('SELECT id, source, target,
cost FROM edge_table',
16,
9,
false,
false);
The preceding query will result in the following: