java - 计算中间有强制点的2个节点之间的最短路径

Question

我正在尝试解决表示地铁服务的双向加权 图中的问题，该图具有大约 300 个节点和 700 条边。

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

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

在我搜索这个问题后，我看到了一些创建子图+应用DFS的建议。所以我创建了一个图表，起点站+强制站+终点站作为新的顶点，边上有每个站之间的最短路径信息+行进所需的时间。

我现在遇到的问题如下:如何在这个新的子图上应用 DFS，使最后访问的站点强制成为我的目的地站点？

抱歉这个问题太长了!

Answer 1

我还有一个想法。由于该图是无环图，我们可以将强制节点(源节点和目标节点除外)拆分为两个节点(A 到 A_start 和A_end) 并在它们之间设置一条边并将权重设置为 -infinity。所有到强制节点 A 的传入边都将连接到 A_start 并且来自强制节点 A 的所有传出边将从 A_end 出来。最后，我们将为源节点到目标节点运行 dijkstra 算法。由于我们在强制节点中设置了一个无限大的权重，dijkstra 必然会遍历它们以最小化成本。另外由于该图是无环图，我们不必担心负循环。