algorithm - 最短路径变化

Question

我正在寻找以下与最短路径相关的问题的解决方案。

给定一个有向图 G = (V,E)，源 s，目标 t1, t2, ..., tk 并且移动边 {i,j} 的成本是 cij。现在我想知道从 s 到 t1, ..., tk 的最短路径。但是，如果使用顶点 v_i(不是源或目标)，那么我们会有额外的 C 成本。请注意，两条路径使用相同的顶点 vi，成本 C 只需支付一次。

Answer 1

如果您正在寻找最短路径，并且如果使用 c 则每条路径都会受到惩罚，那么:

创建修改后的权重函数:

w'(u,v) = w(u,v) + C    if v == c
w'(u,v) = w(u,v)        otherwise

运行dijkstra's algorithm时很容易看出或 Bellman Ford ，对于 w'，任何使用 c 的路径都会受到 C 的惩罚，因为如果 c 出现在路径中- 它只出现一次，所以 C 被添加到总权重中 [注意 c 在最短路径中不能出现超过一次]，当然没有惩罚如果此路径中未使用 c。

---

编辑:我不确定我是否理解正确，如果@SaeedAmiri 提到的是正确的，并且如果你只想给出一次惩罚[并最小化路径的总和to t1,...,tk] 那么你应该使用不同的解决方案 - 具有类似的想法:

创建一个权重函数 w' 使得:

w'(u,v) = w(u,v) + C + epsilon    if v == c
w'(u,v) = w(u,v)                  otherwise

请注意，重要的是 epsilon 是一个只能在 w' 上实现的小尺寸，并且是可能的最小尺寸。

1. 使用 w 在图上运行 dijkstra 或 BF，让我们将权重表示为 W1
2. 使用 w' 在图中运行 dijkstra 或 BF 让我们将权重表示为 W2
3. 如果 W1[ti] == W2[ti] 对于每个 ti ∈ { t1, ..., tk } - 那么你不需要 c最短路径，总结果为 SUM(W1[ti])
4. 否则 - 结果为 min { SUM(W1[ti]) + C , SUM(W2[ti])`

第 4 步背后的想法是您有两种可能性:

• 您可以在不使用 c 的情况下访问所有 t1, ... , tk ，并且它比使用它的路径更便宜，因此您返回 W2 的总和。
• 或者，如果忽略 c - 只会更广泛 - 因此你可以自由使用它[并返回 W1 的总和]，并且只添加一次惩罚。