Q:

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

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?

A:

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.

