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