最短路径变化

Question

我正在寻找解决以下问题，与最短路径有关的问题。给定一个有向图G =（V，E），源s，目标t 1，t 2，...，tk，并且行进边{i，j}的成本为cij。现在我想知道从s到t1，...，tk的最短路径。但是，如果使用vertext v _i（不是源或目标），那么我们有额外的成本C.请注意，两条路径使用相同的vertext vi，成本C只支付一次。

Answer 1

标准为O（n^3）动态规划解决方案...

http://en.wikipedia.org/wiki/Dijkstras_algorithm

...仍然有效，只有一个小的调整：

才算直接邻接矩阵成本，然后通过考虑快捷方式进行迭代，但是在计算vi上的快捷方式添加成本时。

创建修改weightning功能：

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

不难看出，

Answer 2

如果您正在寻找最短路径，每条路径是，如果用c然后penaltised当运行dijkstra's algorithm或Bellman Ford时，使用w'任何使用c的路径都会受到C的惩罚，因为如果c出现在路径中 - 它看起来只有一次，因此C被添加到总重量中[注意c在最短路径中不能出现多次]，当然如果c未在此路径中使用，则不会有任何处罚。

---

编辑：我不知道我的理解正确，如果有什么@SaeedAmiri被提的是正确的，并且如果你想给的惩罚只有一次[和路径总和最小化到T1， ...，TK]那么你应该使用不同的解决方案 - 用类似的想法：

创建weightning函数w”，使之：

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

注意，重要的是小量是一个小尺寸，只能在w'上实现，并且尺寸最小。与w图表

1. 运行Dijkstra算法或BF，让我们表示权重，如结合w'图表 W1
2. 运行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步的想法是你有两种可能性：

• 你可以得到所有的T1，...，TK不使用c，它会更便宜，然后使用具有路径它，所以你返回W2的总和。
• 或者，如果忽略c - 只会更加宽广 - 因此您可以自由使用它[并返回W1的总和]，并仅添加一次惩罚。

Answer 3

你还没有告诉我们到底是什么问题，但有一个明确的片段，承认了一个保守的客观保留减少。

对于集合封面的任意实例，为每个集合设置一个包含源，顶点和每个元素顶点的图。终端t1，...，tk是元素顶点。每个集合顶点的权重为0的边和与其元素对应的顶点的权重为零。在这张图上，我们必须购买一套封面以便从源头到达终端，并且每套封面都足够了。

除非有你可以告诉我们的关于你的实例的东西，多项式时间算法的近似比率不会比Theta（log n）好，所以我建议整数编程。