algorithm - 最短路径变化

Question

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

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

Answer 1

If you are looking for the shortest path, and each path is penaltised if using c then:

Create a modified weightning function:

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

It is easy to see that when running dijkstra's algorithm or Bellman Ford, with w' any path that uses c is penaltized by exactly C, since if c appears in the path - it appears exactly once, so C is added to the total weight [note that c cannot appear more then once in a shortest path], and of course there is no penalty if c is not used in this path.

---

EDIT: I am not sure I understood correctly, if what @SaeedAmiri is mentioning is correct, and if you want to give the penalty only once [and minimize the total sum of paths to t1,...,tk] Then you should use a different solution - with a similar idea:

create a weightning function w' such that:

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

Note that it is important epsilon is a small size that can be achieved only on w', and is the smallest possible size.

1. Run dijkstra or BF on the graph with w, let's denote the weights as W1
2. Run dijkstra or BF in the graph with w' let's denote the weights as W2
3. If W1[ti] == W2[ti] for each ti ∈ { t1, ..., tk } - then you don't need c in the shortest paths, and the total result is SUM(W1[ti])
4. Otherwise - the result is min { SUM(W1[ti]) + C , SUM(W2[ti])`

The idea behind step 4 is you got two possibilities:

• You can get to all of t1, ... , tk without using c, and it will be cheaper then using a path with it, so you return the sum of W2.
• Or, if ignoring c - will only be more expansive - thus you use it freely [and return the sum of W1], and add the penalty only once.

Answer 2

您还没有确切地告诉我们问题出在哪里，但是有一个明确的片段承认从设置的掩护中进行了保持客观的减少。

对于集合覆盖的任意实例，使用源、每个集合的顶点和每个元素的顶点建立一个图。终端 t1, ..., tk 是元素顶点。每个集合顶点到源和与其元素对应的顶点的权重为零的边。在这个图表上，我们必须购买一套覆盖物才能从源头到达终端，每套覆盖物就足够了。

除非您可以告诉我们有关您的实例的信息，否则多项式时间算法的近似比率不会比 Theta(log n) 好，所以我建议使用整数编程。

Answer 3

标准的 O(n^3) 动态规划解决方案...

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

...仍然有效，只需稍作调整：

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