One_to_many Dijkstra To review - pgRouting/pgrouting GitHub Wiki

KDijkstra is a modified "shortest_path". It is simply adapted it to allow 1_to_n requests; it also uses boost_dijkstra...
It can be very useful if you want to generate a distance matrix; it is an alternative I would place between APSP and the standard shortest_path.

---

To install it

You can extract the contents of this in your /extra directory and add KDijkstra in its CMakeLists.txt.

Then CMake (with your prefered options) and make && sudo make install. In my case, I also have to sudo -u postgres -i -H in order to psql 'yourDB' -f /extra/KDijkstra/sql/routing_tomany.sql but I think my installation is somehow incomplete...

---

To use it

Two functions are created: KDijkstra_dist_sp and KDijkstra_ways_sp. They have the same definition as shortest_path except the target ID is now an integer array.

An calling example of KDijkstra_dist_sp is

SELECT * FROM KDijkstra_dist_sp
    ('SELECT gid AS id, source::int4, target::int4, length::double precision AS cost,
      length::double precision AS reverse_cost FROM ways', 
      302946, 
      '{33502, 68355, 54441, 334173, 269543}', 
      true, true);

(where numeric_values are vertex_ids, as in shortest_path)

which returns something like

  vertex_id_source | edge_id_source | vertex_id_target | edge_id_target |       cost           
 ------------------+----------------+------------------+----------------+------------------    
            302946 |         525573 |            33502 |         323014 | 22.1159962156411    
            302946 |         525573 |            68355 |         102211 | 67.0917688766916    
            302946 |         525573 |            54441 |          81084 | 18.5974764093379    
            302946 |             -1 |           334173 |             -1 |               -1    
            302946 |         525573 |           269543 |         456309 | 60.6527591117673    
 (5 rows)

Note that the 4th line contains '-1', reason is that the target cannot be reached.

KDijkstra_ways_sp has the same structure but its answer contains a 6th column, defined as "the_way::text", which is a list of the ids composing the path, separated with commas. If no path is found, the_way will be "NOT FOUND".

Thus the request

SELECT * FROM KDijkstra_ways_sp('SELECT gid AS id, source::int4, target::int4, 
    length::double precision AS cost,length::double precision AS reverse_cost FROM ways',
    302946, '{302950, 334173}', true, true);

returns

 vertex_id_source | edge_id_source | vertex_id_target | edge_id_target |       cost        |                                        the_way                                         
------------------+----------------+------------------+----------------+-------------------+----------------------------------------------------------------------------------------
           302946 |         525573 |           302950 |         525595 | 0.702364018182816 | 525573, 525587, 301720, 301719, 525577, 525578, 301844, 301795, 301796, 377957, 525595
           302946 |             -1 |           334173 |             -1 |                -1 | NOT FOUND
(2 rows)

You can build the geometry later, using for example

SELECT ST_UNION(ww.the_geom) 
    FROM ways ww 
    WHERE gid IN ( <paste (the_way) as previously returned here> );`

---

First tests

By calling psql through a C++ program and libpq-fe, I compared the processing time needed to call the usual shortest_path function n times versus calling KDijkstra_dist_sp once with n targets. First tests give:

n               |    shortest_path               |       kdijkstra_dist  
12              |    87 sec.                     |        9 sec.  
25              |    360 sec.                    |        18 sec.  
50              |    1377 sec.                   |        32 sec. 

Hope it helps...