我试图在加权多向图中找到最短路径(最便宜(，其中顶点是城市，边是城市之间的路线，权重是价格。
每条路线/边缘由3家公司中的一家拥有。一家公司拥有的所有边缘的价格都是一样的。因此，公司"A"拥有的所有边缘都将有X.的价格
因此，如果一条最终路径经过a公司的2条路线和B公司的1条路线，那么最终价格是2a价格+1B价格。此外，优势的权重只是关联公司的价格。
到目前为止，这是一个正常的情况，然而，以下额外的规则让我很难：
第三家公司"C"应用其价格一次，无论其最终路径上有多少条路线，但其价格通常高于前几家公司。因此，C的路线最适合较长的路径，而A和B最适合较短的路径。
以下是我迄今为止所做的(以及为什么它不起作用(：
我使用Dijkstra来获得最便宜的路径，我只需将每条边的权重设置为公司的价格。即使是C.
然后，如果该算法访问C拥有的节点，它会将C拥有的所有其他边的权重设置为0。否则，算法继续正常运行。
问题是，Dijkstras算法总是优先考虑眼前的最佳选择，由于A和B公司的价格比C公司低，因此它会尽量避免C公司。有时，这会导致算法认为最短/最便宜的路径，但实际上，如果它一开始就选择C公司，可能会便宜得多。
在这种情况下，我如何才能获得真正最便宜的路径？
我应该换一种算法吗？如果是，是哪一个？
这里的一个选项是转换航班的原始图，以直接编码这样一种想法，即一旦您乘坐了C航班，未来所有的C航班都是免费的。
对于每个机场x，创建两个节点x1和x2。其思想是，节点x1对应于在机场x中从未乘坐过C航班，而x2则对应于在x机场中至少乘坐过一次C航班。
现在按如下方式添加边。对于价格为p的从机场x到机场y的每一次A或B航班，在价格为p时从x1到y1添加一条边，在价格p时从x2添加到y2。这些对应于按既定价格乘坐A和B航班。然后，对于从机场x到机场y的每一次C航班，价格为p，从x1到y2(这是您支付使用C航班的一次性费用的地方(，以及从x2到y2(价格为0，现在您已经支付使用C飞机的前期费用，该航班是免费的(。
如果你在这个修改后的图中从节点x1开始运行Dijkstra的算法，你可以通过查看到达y1(不使用任何C航班(和y 2这使输入图的大小增加了一倍，这将略微减慢Dijkstra的算法，但不会渐进地影响运行时间。
我认为您可以在每个节点的成本旁边保留一个标志，指示您是否已经使用了C航班。此标志将决定下一次C航班是否需要您付费。
换句话说，当使用C边时，不要将所有C边设置为零，而是将其保持为每个尝试路径的状态的局部值。
您可以将设置了标志的路径优先于其他成本相同但未设置标志的路径。这是一种启发式方法，可以帮助您的算法更快地找到解决方案，但它最终还是会这样做的。
现在，当您启动Dijkstra时，一旦A或B路径的倍数的成本至少与包含C的C路径的成本一样高，则包含C成本的路径将出现在优先级队列中。据我所知，这只是一个标准的Dijkstra。