Find shortest path without going through a specific vertex

3
votes

Given a directed unweighted graph G, a set B of blue vertices in V and a yellow vertex y in (V-B), I need to find the shortest path from a given source s to all other vertices in the graph, without visiting the yellow vertex after visiting a blue vertex. In other words, it is not allowed to visit the yellow vertex if a blue vertex has already been visited (it is possible that some vertices will not be reachable).

Here are my thoughts:

  1. Run BFS(s) a little differently - If we pass at a vertex b which is in B, don't continue the search on b's neighbors. When BFS finishes, if all vertices have been labeled, we are done. Otherwise:

  2. Run BFS(b) on every b in B. For every path from b to y, delete the last edge in the path. For example, the BFS(b) found a path b,s,y then delete (s,y).

  3. Run BFS(s).

Complexity would be O(|B||E|) because we would run BFS(b) |B| times.

I have a feeling this solution is not the best but this is what I came up with. Did I miss anything ?

1
algorithmgraphshortest-pathbreadth-first-search
At step 3, there could be another path from s that passes through y, so this does not work correctly. Even if you remove y entirely, your algorithm will still fail for graphs like this. You need a completely different approach. - BlueRaja - Danny Pflughoeft
@BlueRaja-DannyPflughoeft I didn't understand why my algorithm doesn't work on the example you gave. In your example, the algorithm finishes after step 1, because we run BFS(s) and we get all the shortest paths from s (When I said "if we pass at a vertex b which is in B, don't continue the search on b's neighbors", I didn't mean we should stop the BFS completely, just not continue the BFS on b, while continuing on the rest). - amitooshacham

1 Answers

2
votes

Consider two graphs:

  1. The A graph contains all vertices and edges except the blue vertices
  2. The B graph contains all vertices and edges except the yellow vertex

Now add a directed edge (of zero weight) from every vertex (except the yellow one) in the A graph to its corresponding vertex in the B graph.

Compute the shortest path from the source in the A graph to vertices in the B graph.

Note that the path can switch from the A to the B graph whenever it wants, but once switched there is no way back! This means that a path can use the yellow vertex, but only if it has never visited a blue node.