Finding two shortest path that are 'distant' in the graph - Computational Science Stack Exchange most recent 30 from scicomp.stackexchange.com 2019-11-19T02:24:46Z https://scicomp.stackexchange.com/feeds/question/5062 https://creativecommons.org/licenses/by-sa/4.0/rdf https://scicomp.stackexchange.com/q/5062 2 Finding two shortest path that are 'distant' in the graph Vees https://scicomp.stackexchange.com/users/3600 2013-01-20T19:04:17Z 2013-03-06T15:33:55Z <p>The problem is as follows: We are given a graph with each edge length 1 and two pairs of vertices (a,b) and (c,d).</p> <p>How to find shortest paths between from a to b and from c to d, with assumption that there is a way of moving through both paths (step by step) such that in any time our agents (the one moving from a to b and the other moving from c to d) will be away from each other by at least k?</p> <p>Edit:</p> <p>To make it more clear:</p> <ul> <li>Agents move separately, so in each step only one agent moves and agent can move few times in row (the other 'waits').</li> <li>We are looking for such paths that the summed length is minimal.</li> <li>Paths are 'valid' if there exists a sequence of agent moves in which at any time agents are at least k distant.</li> </ul> <p>We can assume that the input is nice, so there always exists the pair of paths that meets conditions.</p> https://scicomp.stackexchange.com/questions/5062/-/5064#5064 0 Answer by Wolfgang Bangerth for Finding two shortest path that are 'distant' in the graph Wolfgang Bangerth https://scicomp.stackexchange.com/users/393 2013-01-20T23:47:25Z 2013-01-20T23:47:25Z <p>I do not know any exact algorithm but I see at least two approaches to approximate an optimal solution:</p> <ul> <li><p>Compute the shortest path \$a-&gt;b\$ and \$c-&gt;d\$ using any of the existing algorithms (e.g., Dijkstra's algorithm). Then simulate the two paths and, if at one step the two agents are too close do one of the following: (i) Detour by one: If agent A is, for example, at vertex \$v\$ and was at \$v'\$ before, then replace the step \$v'-&gt;v\$ by \$v'-&gt;v''-&gt;v'\$ if you can where \$v''\$ has maximal distance from the position of agent B at that time but has distance one from both \$v\$ and \$v'\$. (ii) If no such \$v''\$ exists that is neighbor to both \$v,v'\$, then simply stay at position \$v'\$ for one more time step.</p></li> <li><p>Find a path through the graph that includes \$a,c,b,d\$ in this order. Then add vertices to this cycle so that the distance between \$a\$ and \$c\$ along your cycle is at least the desired separation \$k\$. The two agents traverse the graph along this common path.</p></li> </ul> <p>My best guess is that if the vertices under consideration are "close" to each other (relative to \$k\$) then the second algorithm will be better. Otherwise, the first algorithm will produce better paths. Both methods find their result in the same complexity as the shortest path finding algorithm.</p> https://scicomp.stackexchange.com/questions/5062/-/5187#5187 1 Answer by hardmath for Finding two shortest path that are 'distant' in the graph hardmath https://scicomp.stackexchange.com/users/651 2013-02-04T14:48:56Z 2013-02-04T14:48:56Z <p>Subject to the OP's clarifications, an exact solution is given by applying Dijkstra's shortest path algorithm to a natural subgraph of a product of two copies of the original graph.</p> <p>Let \$V\$ be the ordered pairs \$(u,v)\$ of original nodes which are "away from each other by at least \$k\$". By assumption both endpoints of the desired agents' path \$(a,c)\$ and \$(b,d)\$ belong to \$V\$.</p> <p>Define edges for \$V\$ as those where two pairs have exactly one coordinate the same and in the other coordinate are nodes connected by an edge of the original graph. That is, if \$v\$ and \$w\$ are connected nodes in the original graph, for any \$u\$ not less than \$k\$ distant from both \$v\$ and \$w\$, then an edge of \$V\$ connects \$(u,v)\$ to \$(u,w)\$ and also an edge of \$V\$ connects \$(v,u)\$ to \$(w,u)\$.</p> <p>As it was clarified one agent "waits" at each step where the other agent moves, it remains only to note that the length of a path from \$(a,c)\$ to \$(b,d)\$ in \$V\$ is simply the sum of path lengths for both agents. Therefore the shortest path in \$V\$ corresponds to this quantity which we desired to minimize.</p>