在加权图中找到最短路径
给定的是城市和气道和道路成本的图形作为每对城市之间的边缘权重。 我们需要找到最小。 考虑到我最多只能通过一次航空公司的限制，从源城市到目的地城市的费用。
目前我的做法是：选择每个气道边缘，然后将dijkstra仅应用于道路边缘的剩余图形。 有什么办法可以改善吗？
构造有向图(G, E)如下：
设X为来源城市， Y为目的地城市。
对于除X以外的每个城市C ，构建两个顶点： (C, yes)和(C, no) ，其中“是”表示“飞机已使用”，“否”表示“飞机未使用”。 对于源城市X ，只构造一个顶点(X, no) 。
边缘如下：
(C, yes)到任何(D, no)都没有优势。 C和D之间存在道路时，从(C, yes)到(D, yes) （对应于(C, no)到(D, no) ）有一条边，并且此边的权重为道路的重量。 C和D之间存在气道时(C, no)从(C, no)到(D, yes)有一个边缘，并且该边缘的重量是气道的重量。 现在，简单地从(X, no)到(Y, yes) （对应于(Y, no) ）找到图G的最短路径，这是使用恰好一条呼吸道（不使用呼吸道） 。 这两个中的最小值将是最终答案。
复杂性将是有向图(G, E)的最短路径问题的复杂性，其中（直到大O常数）具有与原始图相同数量的顶点和边。
根据这个wiki页面，这个问题可以在O(E+VloglogV)时间内解决。 您当然可以使用Dijkstra来简化。
如果可以计算两个城市之间的直线距离，则可以使用A *而不是Dijkstra，将距离函数用作启发式。 当然，与Dijkstra相比，您将扩展更少的节点。
关于航空公司，你的方法听起来很好。
按以下方式创建辅助有向图G'th。
对于主图G中的每个城市V，将两个城市V'和V''添加到G'。
对于G中的每条公路VW，向G'添加四条单向道路V'W'，W'V'，V''W''，W''V''。
对于G中的每个空气连接VW，将两个单向连接V'W''和W'V''添加到G'。
生成的图形被分为两个子图，这样你就只能通过空气从第一个子图移动到第二个子图，而不能返回。 这确保您最多可以使用一次空气，例如最多一次。
你可以在G'上运行Dijkstra算法。 现在G中S和T之间的最短路径将对应于G'中两条路径中较短的一条：S'和T'之间的一条（仅地面）和S'和T“之间的一条（恰好一个空气传输）。
链接地址: http://www.djcxy.com/p/35233.html