2

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.

Paths returned by pgr_KSP for k =1, k =2, k=3strong text

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
)

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.