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%20Medal's gravatar image

Hugh Medal
accept rate: 0%

edited 01 Mar '13, 05:50


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

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%20Trick's gravatar image

Mike Trick ♦♦
accept rate: 21%

edited 01 Mar '13, 14:04

Your answer
toggle preview

Follow this question

By Email:

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



Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "Title")
  • 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



Asked: 28 Feb '13, 21:50

Seen: 1,177 times

Last updated: 01 Mar '13, 14:04

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