在加权图中找到最短路径
finding shortest path in a weighted graph
给定的是城市图以及作为每对城市之间的边权重的航空公司和公路成本。我们需要找到最小值。考虑到我最多只能通过一次航空公司旅行的限制，从源城市到目的地城市的旅行成本。
到目前为止我的方法：选择每个航线边缘一次，然后将 dijkstra 应用于仅在道路边缘上的剩余图形。有什么办法可以改善吗？
如果你可以计算两个城市之间的直线距离，你可以使用 A* 而不是 Dijkstra，使用距离函数作为启发式。与 Dijkstra 相比，您肯定会扩展更少的节点。
关于气道，你的方法听起来不错。
构造一个有向图(G, E)如下：
设X为来源城市，Y为目的地城市。
对于除X以外的每个城市C，构造两个顶点：(C, yes)和(C, no)，其中"yes"表示"airplane used"和"no" 表示 "airplane unused"。对于源城市X，只构造一个顶点(X, no).
边缘如下：
- 没有从任何
(C, yes) 到任何 (D, no) 的边。
- 当且仅当
C 和D，这条边的权重就是车行道的权重。
- 从
(C, no)到(D, yes)有一条边当且仅当C和D之间有气道，这条边的权值就是权值气道。
现在，只需在图 G 中找到从 (X, no) 到 (Y, yes)（相应到 (Y, no)）的最短路径，这就是使用 exactly 的最小成本一条气道（分别使用无气道）。这两个中的最小值将是最终答案。
复杂度将是有向图的最短路径问题的复杂度(G, E)，它（最大 O 常数）与原始图具有相同数量的顶点和边。
根据this wiki page，这个问题可以在O(E+VloglogV)时间内解决。为了简单起见，您当然可以使用 Dijkstra。
按照以下方式创建辅助有向图G'。
对于主图 G 中的每个城市 V，将两个城市 V' 和 V'' 添加到 G'。
对于G中的每条道路VW添加4条单行道V'W', W'V', V''W'', W''V'' to G '.
对于 G 中的每个空气连接 VW 添加两个单向连接 V'W'' 和 W'V'' 到 G'。
生成的图被定向并划分为两个子图，因此您只能乘飞机从第一个子图到第二个子图，而不能返回。这确保您最多可以使用一次空气。
您可以运行 G' 上的 Dijkstra 算法。现在 G 中 S 和 T 之间的最短路径将对应于 G' 中两条路径中较短的一条：一条在 S' 和 T' 之间（仅地面），一条在 S' 和 T'' 之间（正好是一次空中传输）。
给定的是城市图以及作为每对城市之间的边权重的航空公司和公路成本。我们需要找到最小值。考虑到我最多只能通过一次航空公司旅行的限制，从源城市到目的地城市的旅行成本。
到目前为止我的方法：选择每个航线边缘一次，然后将 dijkstra 应用于仅在道路边缘上的剩余图形。有什么办法可以改善吗？
如果你可以计算两个城市之间的直线距离，你可以使用 A* 而不是 Dijkstra，使用距离函数作为启发式。与 Dijkstra 相比，您肯定会扩展更少的节点。
关于气道，你的方法听起来不错。
构造一个有向图(G, E)如下：
设X为来源城市，Y为目的地城市。
对于除X以外的每个城市C，构造两个顶点：(C, yes)和(C, no)，其中"yes"表示"airplane used"和"no" 表示 "airplane unused"。对于源城市X，只构造一个顶点(X, no).
边缘如下：
- 没有从任何
(C, yes)到任何(D, no)的边。 - 当且仅当
C和D，这条边的权重就是车行道的权重。 - 从
(C, no)到(D, yes)有一条边当且仅当C和D之间有气道，这条边的权值就是权值气道。
现在，只需在图 G 中找到从 (X, no) 到 (Y, yes)（相应到 (Y, no)）的最短路径，这就是使用 exactly 的最小成本一条气道（分别使用无气道）。这两个中的最小值将是最终答案。
复杂度将是有向图的最短路径问题的复杂度(G, E)，它（最大 O 常数）与原始图具有相同数量的顶点和边。
根据this wiki page，这个问题可以在O(E+VloglogV)时间内解决。为了简单起见，您当然可以使用 Dijkstra。
按照以下方式创建辅助有向图G'。
对于主图 G 中的每个城市 V，将两个城市 V' 和 V'' 添加到 G'。
对于G中的每条道路VW添加4条单行道V'W', W'V', V''W'', W''V'' to G '.
对于 G 中的每个空气连接 VW 添加两个单向连接 V'W'' 和 W'V'' 到 G'。
生成的图被定向并划分为两个子图，因此您只能乘飞机从第一个子图到第二个子图，而不能返回。这确保您最多可以使用一次空气。
您可以运行 G' 上的 Dijkstra 算法。现在 G 中 S 和 T 之间的最短路径将对应于 G' 中两条路径中较短的一条：一条在 S' 和 T' 之间（仅地面），一条在 S' 和 T'' 之间（正好是一次空中传输）。