algorithm - 加权图的最短路径，但权重有点特殊

Question

我试图在加权多向图中找到最短路径(最便宜)，其中顶点是城市，边是城市之间的路线，权重是价格。

每条路线/边缘由 3 家公司之一拥有。一家公司拥有的所有边缘的价格都相同。因此，公司“A”拥有的所有边缘的价格将为 X。

因此，如果最终路径经过 A 公司的 2 条路线和 B 公司的 1 条路线，则最终价格为 2PriceofA + 1PriceOfB。此外，优势的权重只是关联公司的价格。

到目前为止，这是一个正常的情况，但是，以下额外的规则让我感到困难:

第三家公司'C'无论其在最终路径中有多少条路线都适用它的价格一次，但它的价格通常高于前面的公司。因此，C 的路线最适合较长的路径，而 A 和 B 的路线最适合较短的路径。

这是我到目前为止所做的(以及为什么它不起作用):

我正在使用 Dijkstra 来获得最便宜的路径，我只是将每条边的权重设置为公司的价格。即使对于 C。

然后，如果算法访问 C 拥有的节点，它将 C 拥有的所有其他边的权重设置为 0。否则算法将照常继续。

问题是 Dijkstras 算法总是优先考虑最近的最佳选择，并且由于公司 A 和 B 的价格比 C 小，那么它会尽量避免 C。有时这会导致算法认为最短的路径/最便宜，但如果一开始就选择 C，实际上可能会便宜得多。

在这种情况下我怎样才能得到真正最便宜的路径？

我应该换成另一种算法吗？如果有，是哪一个？

Answer 1

这里的一个选择是将原始航类图转换为直接编码这样的想法，即一旦您乘坐了 C 航类，所有 future 的 C 航类都是免费的。

对于每个机场 x，创建两个节点 x₁ 和 x₂。这个想法是，节点 x₁ 对应于在机场 x 中，但从未乘坐过 C 航类，而 x₂ 对应于在机场 x 中至少乘坐过一次 C飞行。

现在按如下方式添加边。对于从机场 x 到机场 y 的每个 A 或 B 航类，价格为 p，从 x₁ 到 y₁ 以价格 p 和从 x _{添加一条边2} 到 y₂ 价格为 p。这些对应于以既定价格乘坐 A 和 B 航类。然后，对于从机场 x 到机场 y 的每个 C 航类，价格为 p，添加一条从 x₁ 到 y₂ 的边，价格为 p(这是你支付的地方使用 C 航类的一次性成本)和从 x₂ 到 y₂ 的价格为 0(此航类是免费的，因为您已经预付了费用使用 C 航类的成本)。

如果您在此修改后的图中从节点 x₁ 开始运行 Dijkstra 算法，您可以通过查看到达 y_{1< 的成本找到飞往机场 y 的最便宜航类/sub>(不使用任何 C 航类)和 y2(至少使用一个 C 航类)。通过新图表的路径将告诉您要乘坐哪些航类。}

这会使输入图的大小加倍，这会稍微减慢 Dijkstra 算法的速度，但不会逐渐影响运行时间。