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?
Create two directed copies of the graph, one without the forbidden nodes. Connect the outgoing edges of the "forbidden" nodes to the second graph.
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.