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
Hugh Medal |

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
At the end, you want distance(target,TRUE)
answered
Mike Trick ♦♦ |

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.

A' is not going to be huge. Probably between 10x10=100 and 20x20=400. Thats a good idea.