1
$\begingroup$

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

You are given a directed Graph $G = (V,E)$, source $s$, targets $t_1, t_2, \cdots , t_k$ and costs $c_{ij}$ for traveling edge $\{i,j\}$. Now, I want to know the shortest paths from $s$ to $t_1, \cdots , t_k$. But, if a vertext $v_i$ (not source or targets) is used then we have an additional cost of $C$. Note that if two paths use the same vertext $v_i$, the cost $C$ is only paid once.

I hope someone can help me with this. I've been struggling with this problem for quite a while now.

Thanks in advance,

Sjoerd

  • 0
    I know. It's quite straightforward if every path pays for every vertex it traverses. But that's not the case. The cost$C$is only paid once.2012-04-17

0 Answers 0