2
$\begingroup$

I have the following problem. Given a directed graph $G=(V,E)$ with edge costs $c_{ij}$ between all edges $\{i,j\}$. We have multiple sources, say $s_1,\dots,s_k$, and one target, say $t$. The problem is to find the lowest combined costs going from $s_1,\dots,s_k$ 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 \le M \le |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 (nice) solution yet.

1) The problem is similar to multiple targets $(t_1,\dots,t_k)$ 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 e.g. Dijkstra computes shortest path from one source to all other vertexes in the graph.

2) 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.

3) The problem of finding the shortest path from one source to one target while vertexes $v_1,\dots,v_k$ 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 $t_1=v_1,\dots,t_k=v_k$.

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?

0 Answers 0