计算中间必须要点的两个节点之间的最短路径 [英] Calculating shortest path between 2 nodes with mandatory points in the middle

问题描述

我正尝试在表示城市服务的按区域加权图中解决问题，该图具有约300个节点和700个边缘.

I'm trying to solve a problem in a bidrectional weighted graph that represents a Metro Service, with around 300 nodes and 700 edges.

节点是由地铁站定义的，边缘是字符串，其中包含它们所属的线的信息以及在该边缘中行进的时间(即边缘的权重).

The nodes are defined by a metro station and the edges are Strings with the info of the line they belong to and the time (being the edge's weight) it takes to travel in that edge.

我必须确定两个站点之间的最快路径，并给出一个无序列表(如果对它们进行了排序，则所有站点之间的最短路径排列就足够了)强制站点，它可以也要经过其他车站

I have to determine the fastest way between 2 stations, given a list of unordered (if they were ordered a permutation of shortest paths between all the stations would be enough) mandatory stations, and it can go through other stations aswell

搜索该问题后，我看到了一些创建子图+应用DFS的建议.因此，我创建了一个图，其中以起点桩号+强制桩号+终点桩号为新顶点，并以带有每个桩号之间最短路径的信息+行驶时间的边缘作为边缘.

After I searched on the issue, I saw some suggestions of creating a sub-graph + applying a DFS. So I created a graph with the beginning station + mandatory stations + end station as the new vertexes, and the edges with the info of the shortest path between each station + the time it takes to travel.

我现在遇到的问题是:我如何在这个新的子图上应用DFS，以使上次访问的站强制成为我作为目的地的站?

The problem I have now is the following: How do I apply a DFS on this new sub-graph that makes the last visited station forcibly the one i have as a destination?

很抱歉，很长的问题！

推荐答案

我有另一个想法.由于该图是非循环图，因此我们可以将必需节点(源节点和目标节点除外)分为两个节点( A 到 A _start )， A _end )并在它们之间设置一条边，并将权重设置为-infinity.强制节点 A 的所有传入边缘都将连接到 A _start ，而强制节点 A 的所有传出边缘都将连接从 A _end 中出来.最后，我们将对源节点到目标节点运行dijkstra算法.由于我们在必选节点中设置了-infinite权重，因此dijkstra必须通过它们以使成本最小化.另外，由于该图是非循环图，因此我们不必担心负循环.

I have another idea. Since the graph is acyclic graph, we can split the mandatory node (except source and destination node) into two node (A to A_start and A_end) and set an edge between them and set the weight as -infinity. All incoming edge to mandatory node A will be connected to A_start and all outgoing edge from mandatory node A will be came out from A_end. Finally we will run a dijkstra algorithm for source node to destination node. Since we set an -infinite weight in mandatory node, dijkstra is bound to go through them to minimize the cost. Also as the the graph is acyclic graph, we don't have to worry about negative cycle.

这篇关于计算中间必须要点的两个节点之间的最短路径的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！