在加权图中寻找最短路径

Question

给出了一张城市和航空及公路之间的边权重成本的图表。我们需要找到从源城市到目标城市的最小旅行成本，但有一个限制条件，即我只能最多乘坐一次航班。

我的方法是：选择每个航空边仅一次，然后仅在公路边上对剩余的图应用Dijkstra算法。是否有任何改进方法？

- helix

---

我认为你的解决方案很好，可能没有更有效的方法来完成它。 - libik

Answer 1

构建一个有向图 (G, E)，步骤如下：

假设 X 是起点城市，Y 是终点城市。

对于每个不是 X 的城市 C，构建两个顶点：(C, yes) 和 (C, no)，其中 "yes" 表示 "使用飞机"，"no" 表示 "未使用飞机"。对于源城市 X，只构建一个顶点 (X, no)。

边的规则如下：

• 从任何一个 (C, yes) 到任何一个 (D, no) 都没有边。
• 如果 C 和 D 之间有道路，则从 (C, yes) 到 (D, yes)（或者从 (C, no) 到 (D, no)）有一条边，其权重为这条道路的权重。
• 如果 C 和 D 之间有航路，则从 (C, no) 到 (D, yes) 有一条边，其权重为这条航路的权重。

现在，只需在图 G 中找到从 (X, no) 到 (Y, yes)（或者到 (Y, no)）的最短路径，即使用恰好一条航路（或者不使用航路）的最小成本。这两者中的较小值将是最终答案。

---

该问题的复杂度将是有向图 (G, E) 的最短路径问题的复杂度，其顶点数和边数与原始图相同（大 O 常数除外）。

根据此 wiki 页面，可以在 O(E+VloglogV) 时间内解决此问题。当然，您也可以简单地使用 Dijkstra 算法。

- WhatsUp

Answer 2

如果您能够计算两个城市之间的直线距离，那么您可以使用A*算法代替Dijkstra算法，并将该距离函数作为启发式。毫无疑问，您扩展的节点数将比使用Dijkstra算法少。

关于航空路线，您的方法听起来不错。

- FrankS101

Answer 3

创建一个辅助的有向图G'，方法如下。

对于主图G中的每个城市V，在G'中添加两个城市V'和V''。

对于G中的每条道路VW，在G'中添加四条单向道路V'W'、W'V'、V''W''、W''V''。

对于G中的每个航空连接VW，在G'中添加两个单向连接V'W''和W'V''。

生成的图是有向的，并分为两个子图，只能通过航空旅行从第一个子图到达第二个子图，不能返回。这确保您最多只能使用一次航空旅行。

您可以在G'上运行Dijkstra算法。现在，在G中S和T之间的最短路径将对应于G'中两条路径中的较短路径：一条是S'和T'之间的路径（仅限地面），另一条是S'和T''之间的路径（恰好一次航空转移）。

- n. m.