# 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?

• Here is the golden rule of dynamic programming (that is how I can it). If you have an extra condition, then add that condition as a parameter to the subproblem. Given that rule, can you come up with an algorithm? Dec 5, 2018 at 18:09
• cross-posted: stackoverflow.com/questions/53636459/… Dec 5, 2018 at 20:20

Create two directed copies of the graph, one without the forbidden nodes. Connect the outgoing edges of the "forbidden" nodes to the second graph.

• Could you be more specific please? Dec 5, 2018 at 17:07
• @Hawklike: I'm not sure what I could be more specific about. You create a new graph that represents the old graph, using the method above, which can be solved by an off-the-shelf pathfinding algorithm. This means you don't need to code your own, and can instead use one that's already been optimized and supports a heuristic (A*). The other answers do not, despite being more complicated. Dec 5, 2018 at 20:19

Here is an answer by hbejgel from the StackOverflow:

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.