Find shortest path that uses exactly one arc in a subset

 2 Let G(N,A) be a graph with nodes set N and arcs set A. Problem: find the shortest path from node i to node j such that the path contains exactly one arc from the set \$A', which is a subset of A. I am guessing this is a well-known problem. Can someone point me to a reference? Thanks! asked 28 Feb '13, 21:50 Hugh Medal 95●8 accept rate: 0% 3 How large is the set $$A'$$? If it's small, you can simply compute shortest paths from $$i$$ to each arc in $$A'$$, and shortest paths from the end of each arc to $$j$$ (noting that you'll have to remove arcs that were in the path from $$i$$ to the arc before doing the second shortest path problem.) Then pick the shortest of these paths. (01 Mar '13, 00:48) Brian Borchers A' is not going to be huge. Probably between 10x10=100 and 20x20=400. Thats a good idea. (01 Mar '13, 05:52) Hugh Medal

 3 You can modify standard shortest path algorithms by keeping two labels at each node i: distance(i,TRUE) and distance(i,FALSE). The TRUE labels track paths that have contained A', the FALSE contains those with no A' edges. At each step, choose the node i with the smallest unhandled label (track the handling of the labels for TRUE and FALSE separately), and update accordingly if (i,j) in A' distance(j,TRUE) = min (distance(j,TRUE), distance(i,FALSE) + d(i,j)) if (i,j) notin A' distance(j,FALSE) = min (distance(j,FALSE),distance(i,FALSE)+d(i,j)) distance(j,TRUE) = min (distance(j,TRUE),distance(i,TRUE)+d(i,j)) At the end, you want distance(target,TRUE) answered 01 Mar '13, 07:26 Mike Trick ♦♦ 1.0k●1●6 accept rate: 21%
 toggle preview community wiki

By Email:

Once you sign in you will be able to subscribe for any updates here

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "Title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported

Tags:

×190
×8
×3

Asked: 28 Feb '13, 21:50

Seen: 1,034 times

Last updated: 01 Mar '13, 14:04

Related questions

OR-Exchange! Your site for questions, answers, and announcements about operations research.