Shortest path variation

 

I'm looking for a solution to the following problem, related to shortest path.

Given a directed Graph G = (V,E), source s, targets t1, t2, ..., tk and the costs for traveling edge {i,j} is cij. Now I want to know the shortest paths from s to t1, ..., tk. BUT, if a vertext vi (not source or targets) is used then we have an additional cost of C. Note that is two paths use the same vertext vi, the costs C is only paid once.

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.

  • Run dijkstra or BF on the graph with w , let's denote the weights as W1
  • Run dijkstra or BF in the graph with w' let's denote the weights as W2
  • 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])
  • 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.

    • The standard O(n^3) dynamic programming solution...

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

    ...still works, with only a minor adjustment:

    Just calculate the adjacency matrix of direct costs and then iterate through considering shortcuts, but when calculating the cost of a shortcut add on vi.

    You haven't told us exactly what the problem is yet, but there's an unambiguous fragment that admits an objective-preserving reduction from set cover.

    For an arbitrary instance of set cover, set up a graph with a source, vertices for each set, and vertices for each element. The terminals t1, ..., tk are the element-vertices. Each set-vertex has edges of weight zero to the source and to the vertices corresponding to its elements. On this graph, we have to buy a set cover in order to reach the terminals from the source, and every set cover suffices.

    Unless there's something you can tell us about your instances, the approximation ratios for polynomial-time algorithms won't be any better than Theta(log n), so I suggest integer programming.

    链接地址: http://www.djcxy.com/p/6004.html

    上一篇: 为什么Dijkstra算法不适用于负权重边缘？

    下一篇: 最短路径变化