我正在使用netwrokx使用Dijkstra算法计算不同顶点之间的最短路径.我有一种情况，我想连接三个不同的顶点(例如，无向图中的A，B和C).首先，我找到从A到B的最短路径，然后我想找到从A到B的最短路径.到目前为止，我已经尝试过计算从A到B路径的所有节点的最短路径长度.到C，然后从给出最小路径长度的节点计算出最短路径.由于路径可能具有多达200到300个节点，因此计算量很大.
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 ?
推荐答案向您的图形添加一个新节点'auxiliary'.对于A-B路径中的每个节点u，从u到'auxiliary'添加一条边.
Add a new node, 'auxiliary' to your graph. For each node u in the A-B path, add an edge from u to 'auxiliary'.
找到从C到'auxiliary'的最短路径.通过删除最后一个节点'auxiliary'截断该路径.这是从C到该路径的最短路径.
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.