Re: [igraph] Shortest path between nodes i and j that must go through node k

[Tamás Nepusz]

> I'm wondering if there is an algorithm which finds the shortest path between
> the nodes i and j of X, which includes at least one node k of Y. More 
> generally,
> is it possible to find the shortest path between i and j, under the 
> constraint that
> this path goes through k ?
Well, the only thing I can think of right now is to find the shortest path from 
i to every point in Y, and the shortest path from every point in Y to j. Then 
you can choose the shortest path by evaluating all possible combinations of i 
-> Y and Y -> j paths. Alternatively, if there is a direct connection from i 
straight to Y and from Y straight to j, you can *approximate* the result by 
removing all the edges not fully contained in Y except the i --> Y and Y --> j 
edges and then run a simple shortest path search.

-- 
T.