0
$\begingroup$

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? enter image description here

$\endgroup$
  • $\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$ – Apass.Jack Dec 5 '18 at 18:09
  • $\begingroup$ cross-posted: stackoverflow.com/questions/53636459/… $\endgroup$ – BlueRaja - Danny Pflughoeft Dec 5 '18 at 20:20
0
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Could you be more specific please? $\endgroup$ – Hawklike Dec 5 '18 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 Dec 5 '18 at 20:19
0
$\begingroup$

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.
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.