
From:  Margaux Le Cam 
Subject:  Re: [igraph] Shortest path between nodes i and j that must go through node k 
Date:  Fri, 5 Apr 2013 10:52:53 0400 
> I'm wondering if there is an algorithm which finds the shortest path betweenWell, 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.
> 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 ?

T.
_______________________________________________
igraphhelp mailing list
address@hidden
https://lists.nongnu.org/mailman/listinfo/igraphhelp
[Prev in Thread]  Current Thread  [Next in Thread] 