最短路径燃料约束问题

Question

我在某个比赛中遇到了这个问题，但一直未能想出解决方案。我的想法是应用迪杰斯特拉算法或其他方法，但并不是很清楚：

“你将得到一个带有所有边都有正权重的城市的加权连通图。一些城市（节点）有加油站，而其他城市则没有。你有一辆油箱容量为C的摩托车。也就是说，油箱加满后，摩托车可以行驶C个单位的距离。在任何一个有加油站的城市里，摩托车都可以加满油箱。找出给定起点和终点之间的最短路径。假设你从满油状态开始。”

我有一种感觉，O(mnlogn)会被接受。

- therealone

---

数据范围是什么？ - Tim Green

我之前看过这个问题，所以我不太记得范围了。对于O(mn logn)，我的感觉是在我第一次看到这个问题时。如果您有不同时间复杂度的解决方案，请随意提出建议。我没有别的想法。 :) - therealone

非常适用于电动汽车;-) - Pavel Gatnar

这是一辆自行车还是一辆汽车？哈哈 - Andrew Scott

Answer 1

基本上，您需要根据自行车到达时剩余的燃料将每个节点n_i分成多个节点，称为(n_i, r)。您不需要一开始就创建所有(n_i, r)，可以实时进行。

然后类似于Dijkstra算法，从节点(n_0, C)开始，每次找到能够以最小距离到达的下一个(n_x, r)。并更新所有连接到(n_x, r)的节点(n_y, ry)。如果n_y有加油站，则ry将重置为C。如果对于n_y，已经存在节点(n_y, r)，且r >= ry，则无需创建新节点(n_y, ry)，只需忽略它即可。

我无法确定运行时复杂度，但这应该足以在比赛中获得AC。

- Tim Green

---

在(n_0,C)之后应该选择哪个节点？我认为您需要在每个节点上存储(distanceTravelled,n_i,r)，并且每次选择具有最小距离的节点。复杂度将是(no_of_nodesCapacity) log (no_of_nodesCapacity)。 - cegprakash

Answer 2

@Tim Green的方法将会创建指数级别（在加油站数量方面）的节点。在这种情况下运行Dijkstra算法会非常缓慢。有一种更快的方法。

---

首先，找出所有加油站之间的距离。还应包括从起点到每个加油站、从每个加油站到终点以及从起点到终点的距离。可以通过多次运行Dijkstra来完成此操作。

这将给您一个从起点到终点的所有可能有效路线的图。只需在此图上再运行一次Dijktra即可得到最终解决方案。

由于每次运行Dijkstra都将是 O（V ² ） （V =城市数量），并且您必须运行 O（G）次（G =加油站数量，Djikstra的一次运行可以找到从一个加油站到所有其他加油站的距离），因此该算法将在 O（V ² G）的时间内运行。

- BlueRaja - Danny Pflughoeft

---

尽管图形稀疏但有许多加油站时，使用约翰逊算法计算所有对最短路径可能更好。 - Nuclearman

@PavelGatnar：哎呀，找到所有加油站之间的距离是*O(V^2G)**。一旦我考虑到这一点，我的答案仍然与你的复杂度相同（尽管在实践中你的速度会稍微快一些）。干得好！ - BlueRaja - Danny Pflughoeft

使用这些距离形成一个图，然后删除所有长度大于C的边。这可能会涉及到很多边，那么不创建它们怎么样（可以通过修改Dijkstra算法的最大距离来实现）？ - Pavel Gatnar

Answer 3

有一种改进的Dijkstra算法，其中加油站顶点之间的距离是通过另一种修改后的Dijkstra算法按需计算的，该算法在指定范围内搜索所有未解决的加油站顶点。

1. 将起点和终点视为加油站。
2. 将起点放入主要优先队列中。
3. 使用子Dijkstra运行主Dijkstra。

主Dijkstra循环执行以下步骤：
0. 当主要优先队列为空时退出，提示“无法到达终点”。
1. 从主要优先队列中取出加油站。
2. 如果它是终点，则退出。
3. 调用子Dijkstra来提供与实际加油站的距离未解决的相邻加油站。

子Dijkstra使用自己的优先队列（直到队列为空）搜索从实际加油站到燃料范围内所有顶点的最短路径，并根据其状态处理已到达的加油站：
* 在主要队列中已解决-不处理出边。
* 在主队列中等待-更新距离（当低于decreaseKey时）和路径
* 否则将其放入主队列中。

- Pavel Gatnar