I am using netwrokx to calculate the shortest path between different vertices using Dijkstra algorithm. I have a case where I want to connect three different vertices (for example A, B and C in an undirected graph). First I find the shortest path from A to B and then I want to find the shortest path from the path of A to B. What I have tried so far is I have calculate shortest path length from all the nodes of the A to B path to C and then I calculate the shortest path from the node which gives the minimum path length. This is computationally intensive as path may have up to 200 to 300 nodes.
Can anyone give me a hint how can I improve approach? or easier way to find the shortest path from the already existing edges to the target ?
Add a new node, 'auxiliary' to your graph. For each node u in the A-B path, add an edge from u to 'auxiliary'.
Find the shortest path from C to 'auxiliary'. Truncate that path by removing the final node 'auxiliary'. This is now the shortest path from C to that path.
More generally, this approach works whenever you want to find the shortest path from a node to a set of nodes and (with a bit of generalization) it finds the shortest path from one set of nodes to another set.
- Find the shortest path X = A to B.
- Find the shortest path Y = A to C.
- Find the shortest path Z = B to C.
- combine the paths.
shortest_path(G, source, target) imported from networkx will return the shortest path between two vertices.
If this method is done by implementing Dijkstra's algorithm, the efficiency is equivalent to Dijkstra's algorithm asymptotically.
