具有边缘代价的Dijkstra最短路径算法

2018-05-31 02:09:45

我有一个定向的，正面的加权图。每条边都有使用成本。我只有一笔钱，我想用dijkstra算法计算最短路径，但路线上的边缘成本总和必须小于或等于A.

我想用最小的Dijstra修改来做到这一点（如果我可以通过对Dijkstra的小修改来完成）。如果可以的话，我必须在O(n*log(n))这样做，但我认为我可以。

任何人都可以帮助我呢？

https://www.spoj.pl/problems/ROADS/

这个问题在CEOI98上给出，其官方解决方案可以在这里找到。

您并不需要修改Dijkstra的算法来做到这一点，因为答案相当于找到最短路径，然后在小于或等于A时接受它。

当然，如果您访问成本高于A的路径，您总是可以将内部环路短路。

编辑：随着澄清，你想最大限度地降低成本和距离，你不能这样做，没有澄清你想要的解决方案。你想要最便宜的路径吗？你想要最短的路径吗？你想要一些成本和距离的功能吗？所有这些决定了您应该为特定边缘使用的权重函数。

链接地址: http://www.djcxy.com/p/5999.html