Variation (complex?) on the shortest path

I have the following problem. Given a directed graph G=(V,E) with edge costs cij between all edges {i,j}. We have multiple sources, say s1,...,sk, and one target, say t. The problem is to find the lowest combined costs going from s1,...sk to t, where the total amount of visited vertexes by all different paths is M. (The sources and target don't count as visited vertexes and 0 <= M <= |V|-k+1, so if M = 0 all paths go directly from source to target.)

I came up with the following, but haven't found a solution yet.

The problem is similar to multiple targets (t1,...,tk) and one source by just reversing all the edges and making the sources targets and the target source. I thought this could be useful since eg Dijkstra computes shortest path from one source to all other vertexes in the graph.

With just one target and one source one can find the shortest path with max. amount of visited vertexes M with the Bellman Ford algorithm. This is done by increasing the number of visited vertexes iteratively.

The problem of finding the shortest path from one source to one target while vertexes v1,...,vk have to be visited can, for small k, be solved as follows: i) compute shortest path between all vertexes. ii) check which of the k! permutations is the shortest. I thought this could be useful when transforming my adjusted problem at 1) into the problem of going from one source to one "supertarget", with mandatory visits at the "old" targets t1=v1,...,tk=vk.

Unfortunately, combining 1, 2 and 3 doesn't provide a solution but it may help. Does anyone know the solution? Can this be solved efficiently?

---

Why not do a separate Dijkstra for each s, and later sum the costs?

Something like:

float totalCost;
for (int i=0; i<k; i++)
  totalCost += Dijkstra(myGraph,s[i],t);

I hope I understood the question correctly.

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

上一篇: Kth最短路径

下一篇: 最短路径上的变化（复杂？）