最短路径变化
我正在寻找解决以下与最短路径有关的问题的解决方案。
给定一个有向图G =（V，E），源s，目标t1，t2，...，tk，并且行进边{i，j}的成本为cij。 现在我想知道从s到t1，...，tk的最短路径。 但是，如果使用了vertext vi（不是源或目标），那么我们会有额外的成本C.请注意，两条路径使用相同的vertext vi，成本C只支付一次。
如果您正在寻找最短路径，并且每条路径在使用c时都会受到处罚，那么：
创建一个修改后的权重函数：
w'(u,v) = w(u,v) + C if v == c
w'(u,v) = w(u,v) otherwise
这是很容易看到，运行Dijkstra算法或贝尔曼福特，与当w'的任何路径使用c正好由penaltized C ，因为如果c出现在路径-它似乎只出现一次，所以C被添加到总重量[注意c在最短路径中不能出现多次]，当然如果在这条路径中不使用c ，则不会有任何处罚。
编辑：我不知道我的理解是否正确，如果@SaeedAmiri提到的是正确的，并且如果你想只给予一次惩罚[并且尽量减少到t1的路径总数，...，tk]，那么你应该使用一个不同的解决方案 - 具有类似的想法：
创建一个权重函数w'，以便：
w'(u,v) = w(u,v) + C + epsilon if v == c
w'(u,v) = w(u,v) otherwise
请注意，重要的是epsilon只能在w'上实现，并且尺寸最小。
w在图上运行dijkstra或BF，让我们将权重表示为W1 w'让我们表示权重W2 W1[ti] == W2[ti]对于每个ti＆lt; {t1，...，tk} - 那么你在最短路径中不需要c ，并且总结果是SUM(W1[ti]) 第4步背后的想法是你有两种可能性：
c - 只会更加广泛 - 因此您可以自由使用它[并返回W1的总和]，并且只加罚一次。 标准的O（n ^ 3）动态编程解决方案...
http://en.wikipedia.org/wiki/Dijkstras_algorithm
...仍然有效，只需稍作调整：
只需计算直接成本的邻接矩阵，然后通过考虑快捷方式进行迭代，但在计算vi上的快捷方式添加成本时。
你还没有告诉我们到底是什么问题，但是有一个明确的片断，承认了一个保守的客观保留减少。
对于集合封面的任意实例，设置一个包含源的图形，每个集合的顶点以及每个元素的顶点。 终端t1，...，tk是元素顶点。 每个集合顶点的权重为0的边和与其元素对应的顶点的权重为零。 在这张图上，我们必须购买一套封面以便从源头到达终端，并且每套封面都足够了。
除非你可以告诉我们关于你的实例的东西，多项式时间算法的近似比率不会比Theta（log n）好，所以我建议整数编程。
链接地址: http://www.djcxy.com/p/6003.html下一篇: Route problem in a graph: minimize average edge cost instead of total cost