给定的是一张城市图以及作为每对城市之间的边权重的航空公司和公路成本。我们需要找到最小值。考虑到我最多只能通过一次航空公司旅行的限制，从源城市到目的地城市的旅行成本。
到目前为止，我的方法是:选择每个航线边缘一次，然后仅将 dijkstra 应用于道路边缘上的剩余图形。有什么办法可以改善吗？
最佳答案
构造一个有向图(G, E)如下:
令 X 为源城市，Y 为目的地城市。
对于除X之外的每个城市C，构造两个顶点:(C, yes) 和(C, no) ，其中“yes”表示“飞机已使用”，“no”表示“飞机未使用”。对于源城市X，只构造一个顶点(X, no)。
边缘如下:
- 从任何
(C, yes)到任何(D, no)都没有边。 - 从
(C, yes)到(D, yes)(resp.(C, no)到(D, no)) 当且仅当C和D之间有道路，这条边的权重就是道路的权重. - 存在从
(C, no)到(D, yes)的边当且仅当C和C之间有气道D，这条边的权重就是气道的权重。
现在，只需找到图 G 中从 (X, no) 到 (Y, yes) 的最短路径(resp.到 (Y, no))，这是仅使用一个气道(resp. 不使用气道)的最低成本。这两个中的最小值将是最终答案。
复杂度将是有向图 (G, E) 的最短路径问题的复杂度，它(最大 O 常数)与原始图具有相同数量的顶点和边.
根据 this wiki page , 这个问题可以在O(E+VloglogV) 时间内解决。为简单起见，您当然可以使用 Dijkstra。
关于algorithm - 在加权图中找到最短路径，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/35918175/