I am trying to get an arbitrary number of paths between two points in a network. I am using pgr_KSP — Returns the “K” shortest paths. My aim is to get the K cheapest routes between two points.
However when I implement it with k = 1 it returns the same result as pgr_dijkstra which is the shortest path, this is the expected and desired result.
When I use it with k=2, I would have expected it to return a paths the included the two cheapest one of which should be the path returned when k=1. The screen shot below shows what is returned for cases of k = 1, 2, 3 The version of pgRouting used is 2.6 The costs returned are
k = 1 - 88899.77
k = 2 - 91758.40: 91980.81
k = 3 - 93202.83: 93922.34: 94149.52
What can I try to get the result where if I used k =3 it would return the paths I am getting from the case where k = 1 and k= 2
edit: What looks like you get for a given k is a value of k you get the Xth to Yth shortest routes where
x = ((k-1)*k/2) +1
y = ((k+1)*k/2)
So for the example where k = 6
X = 16
Y = 21.
The Code I have to generate these paths is:
DROP TABLE if EXISTS ksp_results; SELECT pk.seq, pk.path_id, pk.path_seq, pk.node, pk.edge, cost, agg_cost,e.geom INTO ksp_results FROM pgr_KSP( 'SELECT gid as id, source, target, length as cost, length as reverse_cost FROM edges', 1, 37, 1, --This is k value directed:=true ) AS pk LEFT JOIN edges as e ON pk.edge = e.gid ORDER BY pk.seq --Now use this to build paths. DROP TABLE if EXISTS ksp_paths; CREATE TABLE ksp_paths AS ( SELECT --cost.seq, cost.path_id, g.no_links, ST_Length(g.geom) as length, cost.agg_cost AS cost, g.geom FROM ( SELECT pk.seq, pk.path_id, pk.path_seq ,agg_cost FROM ksp_results AS pk WHERE pk.edge = -1 ) AS cost INNER JOIN ( SELECT pk.path_id, MAX(pk.path_seq) AS no_links, ST_Union(geom) AS geom FROM ksp_results AS pk WHERE pk.edge != -1 GROUP BY pk.path_id ) AS g ON cost.path_id = g.path_id )