| | 1 | = pgrouting with Dijkstra algorithm = |
|---|
| | 2 | |
|---|
| | 3 | Dijkstra algorithm was the first algorithm implemented in pgRouting. |
|---|
| | 4 | It doesn't require more attributes than source and target ID, and it can |
|---|
| | 5 | distinguish between directed and undirected graphs. You can specify if your |
|---|
| | 6 | network has "reverse cost" or not. |
|---|
| | 7 | |
|---|
| | 8 | {{{ |
|---|
| | 9 | shortest_path( sql text, |
|---|
| | 10 | source_id integer, |
|---|
| | 11 | target_id integer, |
|---|
| | 12 | directed boolean, |
|---|
| | 13 | has_reverse_cost boolean ) |
|---|
| | 14 | }}} |
|---|
| | 15 | |
|---|
| | 16 | Note: |
|---|
| | 17 | * Source and target IDs are node IDs. |
|---|
| | 18 | * Undirected graphs ("directed false") ignores "has_reverse_cost" setting |
|---|
| | 19 | |
|---|
| | 20 | |
|---|
| | 21 | == Shortest Path Dijkstra core function == |
|---|
| | 22 | |
|---|
| | 23 | Each algorithm has its core function (implementation), which is the base for its |
|---|
| | 24 | wrapper functions. |
|---|
| | 25 | |
|---|
| | 26 | {{{ |
|---|
| | 27 | SELECT * FROM shortest_path(' |
|---|
| | 28 | SELECT gid as id, |
|---|
| | 29 | source::integer, |
|---|
| | 30 | target::integer, |
|---|
| | 31 | length::double precision as cost |
|---|
| | 32 | FROM ways', |
|---|
| | 33 | 10, 20, false, false); |
|---|
| | 34 | |
|---|
| | 35 | }}} |
|---|
| | 36 | |
|---|
| | 37 | {{{ |
|---|
| | 38 | vertex_id | edge_id | cost |
|---|
| | 39 | -----------+---------+--------------------- |
|---|
| | 40 | 10 | 293 | 0.0059596293824534 |
|---|
| | 41 | 9 | 4632 | 0.0846731039249787 |
|---|
| | 42 | 3974 | 4633 | 0.0765635090514303 |
|---|
| | 43 | 2107 | 4634 | 0.0763951531894937 |
|---|
| | 44 | ... | ... | ... |
|---|
| | 45 | 20 | -1 | 0 |
|---|
| | 46 | (63 rows) |
|---|
| | 47 | }}} |
|---|
| | 48 | |
|---|
| | 49 | == Dijkstra Wrapper functions == |
|---|
| | 50 | |
|---|
| | 51 | Wrapper functions extend the core functions with transformations, bounding box |
|---|
| | 52 | limitations, etc.. |
|---|
| | 53 | |
|---|
| | 54 | === Wrapper WITHOUT bounding box === |
|---|
| | 55 | |
|---|
| | 56 | Wrappers can change the format and ordering of the result and they often set |
|---|
| | 57 | default function parameters and make the usage of pgRouting more simple. |
|---|
| | 58 | |
|---|
| | 59 | {{{ |
|---|
| | 60 | SELECT gid, AsText(the_geom) AS the_geom |
|---|
| | 61 | FROM dijkstra_sp('ways', 10, 20); |
|---|
| | 62 | }}} |
|---|
| | 63 | |
|---|
| | 64 | {{{ |
|---|
| | 65 | gid | the_geom |
|---|
| | 66 | --------+--------------------------------------------------------------- |
|---|
| | 67 | 293 | MULTILINESTRING((18.4074149 -33.9443308,18.4074019 -33.9443833)) |
|---|
| | 68 | 4632 | MULTILINESTRING((18.4074149 -33.9443308,18.4077388 -33.9436183)) |
|---|
| | 69 | 4633 | MULTILINESTRING((18.4077388 -33.9436183,18.4080293 -33.9429733)) |
|---|
| | 70 | ... | ... |
|---|
| | 71 | 762 | MULTILINESTRING((18.4241422 -33.9179275,18.4237423 -33.9182966)) |
|---|
| | 72 | 761 | MULTILINESTRING((18.4243523 -33.9177154,18.4241422 -33.9179275)) |
|---|
| | 73 | (62 rows) |
|---|
| | 74 | }}} |
|---|
| | 75 | |
|---|
| | 76 | === Wrapper WITH bounding box === |
|---|
| | 77 | |
|---|
| | 78 | You can limit your search area by adding a bounding box. This will improve |
|---|
| | 79 | performance especially for large networks. |
|---|
| | 80 | |
|---|
| | 81 | {{{ |
|---|
| | 82 | SELECT gid, AsText(the_geom) AS the_geom |
|---|
| | 83 | FROM dijkstra_sp_delta('ways', 10, 20, 0.1); |
|---|
| | 84 | }}} |
|---|
| | 85 | |
|---|
| | 86 | Note: The projection of OSM data is "degree", so we set a bounding box |
|---|
| | 87 | containing start and end vertex plus a 0.1 degree buffer. |
|---|
