-1
$\begingroup$

Given an undirected graph with positive weights, there are 2 kinds of edges: locked edges and unlocked edges. Determination if a given edge is either locked or unlocked edge takes O(1).

For given two vertices s , t and a positive number k = O(1), How can I find the shortest path between s and t which contains at most k locked edges? How to find that path if it must contains exactly k locked edges? note that the second path might be contains the same locked edge more than 1 time.

So my first solution was to define a counter that is initialized to k, and decrease its value each time I found locked edge during dijkstra algo. but it doesn’t meet the requirement, so @tmyklebu suggest me to copy the graph k times, and modify each graph to directed one so that a locked edge vw in G_i turns into an edge from u in G_i to v in G_{i+1} and from v in G_i to u in G_{i+1}. I didn’t undertand this solution, so I hope you can help (or suggest another one to solve this problem) :-)

Thanks a lot!
Tomer.

$\endgroup$
1
$\begingroup$

I hope the following makes the solution clearer. Suppose the set of locked edges is $L$ and the set of unlocked edges is $U$. Let $G_U$ be the graph with the same vertex set as $G$ but the edge set is $U$. Now make k+1 copies of $G_u$. Since we now have $k+1$ copies of a vertex $v$, lets call them $v_1 \ldots v_{k+1}$.

Now add edges between the copies as follows. There is an edge between $u_i,v_{i+1}$ iff there exists a corresponding edge $u,v$ in G and the edge $u,v$ is locked. Now note that in this new graph we make a transition from one copy to the next copy if and only if we take a locked edge.

Now lets start a path from vertex $S_1$ in the first copy and lets say we are at a vertex $V_{i+1}$ in the $(i+1)^{th}$. Note that this means that we must have already traversed exactly $i$ locked edges. Therefore if we want to travel exactly $k$ locked edges we need to find a shortest path from $S_1$ to $T_{k+1}$.

Another way to think of what this path would look like is that imagine the required shortest path and cut it off into pieces where the locked edges. Now you can see that in your path the pieces in between the $i^{th}$ locked edge and the $(i+1)^{th}$ locked edge happen in the $(i+1)^{th}$ and each locked edge moves you to another segment. Hope this helps.

If you want the shortest path with atmost k edges you can look for the shortest path from S to $T_1,T_2 \ldots T_{k+1}$ and take the minimum.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.