Finding shortest path between two nodes with a set of forbidden nodes

0
votes

I have undirected and unweighted graph, in which I would like to find the shortest path between two entered nodes. There is also a set of forbidden nodes. How to find the shortest path, if I am allowed to visit at most one node from the set of forbidden nodes?

enter image description here

4
algorithmgraphshortest-path
BFS, storing current node and if you already visited a forbidden node - juvian
@juvian This might not work even in the graph above. You cannot simply store a flag which determines if you already visited a forbidden node. - Hawklike
@Hawklike: please explain why you can't do that. You're the programmer: you can store any state information you wish. This is not a global flag: it's a flag associated with the node. I agree that it won't work, but not for the reasons you state. - Prune
@Hawklike its a bit more complex, need a 2 level bfs. Still, posted a simpler answer for the case of only at most 1 forbidden node. - juvian
Cross-posted: cs.stackexchange.com/questions/101063/… - BlueRaja - Danny Pflughoeft

4 Answers

1
votes

  1. Do a BFS starting from END - Whenever it reaches a Forbidden node, update its distance_from_end and don't add its neighbors to your queue. All forbidden nodes that are not visited should not have a valid distance_from_end.

  2. Do the same as (1) but starting from START and updating distance_from_start

  3. For all forbidden nodes take the one with minimal distance_from_start + distance_from_end. (note that this node may not exist since nodes can have non valid values in those fields and thus should be disconsidered)

  4. Do a BFS from start to finish, disconsider all forbidden nodes except the one found in (3).

  5. From the BFS performed in 4 you'll either:

    • find a path that does not cross any forbidden node which is shorter than the one that would cross it.
    • find a path that does cross the forbidden node, in this case its length should be equal to (distance_from_start + distance_from_end) for that node.
    • find no path at all, meaning that you did not find a node in step (3) and that after removing all forbidden nodes from the graph, you get a graph where START and END are in different partitions.
1
votes
  • Make a BFS from start, don´t go over forbidden nodes.
  • Make a BFS from end, don´t go over forbidden nodes.
  • Initialize path distance as dist(start, end). This will be infinite if your first bfs didn´t reach end.
  • For each forbidden node, do path distance = min(path distance, dist(start, forbidden node) + dist(end, forbidden node))
  • Return path distance

Complexity: same as BFS

0
votes

You can do a first BFS that list the reachable Forbidden nodes from start (but cannot cross it). Then you record the distance from start. In your example 2 for each forbidden node.

You do the same from end node giving distances 2 and 1 on your path.

Then you unforbbid the best forbidden node (minimum distance from start+distance from end). And you finally do a BFS in the full graph.

You can eventually save the path to all forbidden nodes to save the last BFS.

0
votes

Perform a BFS, but with the graph as a parameter, rather than as a global reference table. On any branch, when you visit a forbidden node, you stop and remove all of the other forbidden nodes from the graph you pass to the next level.

In fact, if you include a list of forbidden nodes as part of your graph structure, that removal can be a trivial iteration.