Can Ksp Algorithm(Shortest Path Algorithm) have a constraint that the suggested paths must include a particular node or link

I am using pgr_ksp algorithm to find out the shortest path between a startnode and endnode by creating a network topology between all the nodes. Pgr_ksp algorithm very well gives me all the shortest paths taking the cost in consideration. But now, I also want to add a constraint that the path its giving between startnode and endnode must include or exclude a particular node or link. Below code works perfect. But how and where can I add a constraint such that the path will include a node for example 'nodeA'?

``````SELECT d.*, f.linkname ,SUM(cost) OVER (PARTITION BY path_id) AS aggregation
FROM pgr_ksp('Select id, source, target, airmiles as cost from f',
source,
target,
2) AS d
INNER JOIN f ON d.edge= f.id
ORDER BY aggregation, path_id, path_seq;
``````
• Could you break it into two shortest path problems? Startnode -> particular node, then particular node -> endnode.
– Jon
Commented Sep 4, 2018 at 20:48
• run the function on those nodes in sequence. e.g. `pgr_ksp(start_node, included_node)` & `pgr_ksp(included_node, end_node)` Commented Sep 4, 2018 at 20:50
• oh, or set the `heap_path` parameter to `true` and select only paths where the desired edge/node is traversed, e.g. as `WHERE` filter? can't test both now...I'd say write a function for the sequencing, but try this first... Commented Sep 4, 2018 at 21:03

I have no experience with the above library, but assuming no additional constraints (like "no edge should be taken more than once"), the shortest path from A to C that includes B is equivalent to the shortest path from A to B, plus the shortest path from B to C.

In other words, run the algorithm twice and combine the results.

• Yes for now I have done the same, wanted to know if pgr_ksp or any shortest path algorithm provides any such functionality internally. Thanks for it though.
– Ash
Commented Sep 4, 2018 at 21:43
• Thanks for your help. Can you also tell me, if I wish to exclude a particular node(such that the path should not be taken in which that node lies). How can that be achieved.
– Ash
Commented Sep 10, 2018 at 17:53
• @Ash: Remove the node? Commented Sep 10, 2018 at 19:21
• In short, I want a path returned by pgr_ksp, which excludes that particular node and returns other paths except the ones having that node.
– Ash
Commented Sep 10, 2018 at 21:44
• @Ash: I understand. I'm saying, remove the node from the graph. Commented Sep 10, 2018 at 21:52

I had a minute and packed that functionality into a function; I more or less sticked to plain SQL here and couldn´t implement some smart moves (like using the original function if the length of the passed array is only 2 or general PL/pgSQL magic), since I haven´t had much time. But it works like a charm.

After creation (make sure it´s the same BD/schema where your pgRouting is installed), you can call this function just like the other `pgr_KSP`, but with an array (type `INT`) as argument instead of `start_vid` & `end_vid`, e.g.

``````SELECT *
FROM pgr_ksp(
<edge_sql>,
ARRAY[<start_vid>, [<via_vid>, ...,] <end_vid>],  --the inner [] mean 'optional'; don´t include them in the array
<k>,
<directed>,         --optional
<heap_paths>        --optional
);
``````

which will return the same set structure, having a continuous path for each matching `path_id` over all `via_vid`s, and with

• no intermediate `-1` edges (marking the end of one function execution and the arrival at an `via_vid`)
• a continuous `path_seq` column (over `path_id`)
• a continuous `agg_cost` column (over `path_id`)

It's absolutely possible I have overseen cases where this doesnt work as expected. Also, having a continuous path based on a common `path_id` might or might not be what you want.

• Thanks for your help. Can you also tell me, if I wish to exclude a particular node(such that the path should not be taken in which that node lies). How can that be achieved.
– Ash
Commented Sep 10, 2018 at 17:52
• two options: 1.) simply exclude it in the `WHERE` filter; this, however, will return no route if there is no alternative to go via that point. 2.) assign humongous cost values (e.g. in a `CASE` construct) to the edges that connect to that node: the route through that node will be returned if it is still the only possible route. Commented Sep 12, 2018 at 10:49