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?
Here is an answer by hbejgel from the StackOverflow:
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.
Do the same as (1) but starting from START and updating distance_from_start
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)
Do a BFS from start to finish, disconsider all forbidden nodes except the one found in (3).
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.