[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
## Re: [igraph] Shortest path between nodes i and j that must go through no

**From**: |
Tamás Nepusz |

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

**Date**: |
Fri, 5 Apr 2013 15:27:52 +0200 |

>* 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.