中间带强制点的两个节点间最短路径的计算

Question

我正试图解决投标加权图中的一个问题，它代表了一个具有大约300个节点和700个边的城域网服务。

节点由地铁站定义，边缘是String，其中包含它们所属的线路的信息，以及在该边缘上移动所需的时间(即边缘的重量)。

我必须确定两个站点之间最快的路径，给出一个无序列表(如果它们被命令在所有站点之间排列最短路径就足够了)，并且它也可以通过其他站点。

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

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

很抱歉有这么长的问题！

Answer 1

首先，你需要为你的问题定义一些东西:为了到达目的地，你需要访问的唯一站点是强制车站吗？或者两者之间是否有其他未知的站点不是强制性的，但可能需要在最短的路径上？

假设此图包含循环：

如果强制站点列表是到达目的地所需的所有站点，则可以使用Dijkstra算法解决所有强制节点的子图问题。

在另一种情况下，它会更复杂(NP-难实际上)-更深入的解决方案- Shortest path that traverses a list of required edges