Finding shortest path where any two nodes from two lists of nodes must be used

Admin 1
Viewed 491

I've implemented a function that uses Dijkstra's algorithm to find the shortest (lowest weight) path from a given source node to any given destination node in a weighted, undirected graph (positive weights).

I've got two lists A and B which each hold at least one node location, and every node they hold is valid (is in the graph). A node in list A can also be in list B and vice versa.

I need to extend my function so that it also takes lists A and B as input, and finds the shortest path from source node to the destination node that uses at least one node from both A and B. Also, while it can use A and B nodes at any point in the path, it must use a B node after it has used an A node (or use a node that is in both A and B).

If a node is in both A and B, it immediately satisfies this requirement.

The source node and destination node can both be in A and/or B.

e.g.

Valid paths (S is source, D is destination, N is node not in A or B):

  • S > A > B > D
  • S > B > A > B > D
  • S > N > B > A > N > B > D
  • S > (A&B) > D
  • S(A) > D(B)

Invalid path:

  • S > B > A > D

How would I be able to extend it so that it keeps the complexity of Dijkstra's algorithm, O(Elog(V))? E being # of edges, V # of vertices. I'm thinking there must be a way I can do it using Dijkstra's algorithm a constant number of times, so the complexity doesn't change. Cheers for any help.

dijkstra python-3.x python
1 Answers

I would recommend extending Dijkstra by keeping track of two more values per node. The shortest path with visiting A and shortest path visiting A>B (A and then B).

Usually, you keep track of the shortest path to each node in Dijkstra. Now, you would keep track of three shortest paths. You would still process single steps and add new neighbors to the queue, but this time, there are three possibilities:

  1. Reached node without visiting A: For all neighbors, that are not in A, update the tentative "without A" distance. For all neighbors, that are in A, update tentative "with A" distance. For all neighbors, that are in A and B, update tentative "A>B" distance.

  2. Reached node visiting A but not B after that: For all neighbors, that are not in B, update tentative "with A" distance. For all neighbors, that are in B, update tentative "A>B" distance.

  3. Reach node visiting A and then B If final node, found result. Otherwise update all neighbors tentative "A>B" distance.

Choose always the node with the smallest tentative distance, as in the original algorithm. For this, it does not matter with which condition you reached the node.

user_121250120
Related