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? 
$\begingroup$ $\endgroup$
2 
- $\begingroup$ 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? $\endgroup$喜欢算法和数学– 喜欢算法和数学2018-12-05 18:09:09 +00:00Commented Dec 5, 2018 at 18:09
- $\begingroup$ cross-posted: stackoverflow.com/questions/53636459/… $\endgroup$BlueRaja - Danny Pflughoeft– BlueRaja - Danny Pflughoeft2018-12-05 20:20:52 +00:00Commented Dec 5, 2018 at 20:20
Add a comment |
2 Answers
$\begingroup$ 
$\endgroup$
2 Create two directed copies of the graph, one without the forbidden nodes. Connect the outgoing edges of the "forbidden" nodes to the second graph.
answered Dec 5, 2018 at 16:29
BlueRaja - Danny Pflughoeft
1,5481 gold badge10 silver badges16 bronze badges
- $\begingroup$ Could you be more specific please? $\endgroup$Hawklike– Hawklike2018-12-05 17:07:36 +00:00Commented Dec 5, 2018 at 17:07
- 1$\begingroup$ @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. $\endgroup$BlueRaja - Danny Pflughoeft– BlueRaja - Danny Pflughoeft2018-12-05 20:19:12 +00:00Commented Dec 5, 2018 at 20:19
$\begingroup$ $\endgroup$
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.