# Shortest path variation

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.

You can use $\TeX$ in dollar signs (single for inline, double for displayed) to typeset your formulas. Subscripts can be produced using underscores, e.g. t_k produces $t_k$ and c_{ij} produces $c_{ij}$. – joriki Apr 17 '12 at 7:30
@dtldarek: I don't think so. He's trying to minimize the cost of each $s\leadsto t_i$ path, not the total cost of all vertices and edges in the shortest-path tree. (Also, technically, Steiner trees are only defined for undirected graphs.) – JeffE Apr 17 '12 at 7:44
@Jeff, I want to minimize the overall costs. So it's basically just Dijkstra where you compute the shortest paths from s to $t_1 ... t_k$. But then with some sort of penalty for using different vertices for the optimal paths. Because for each vertex which is not s or $t_1 ... t_k$ and which is in one or more paths you pay and extra cost C. – sjoerd999 Apr 17 '12 at 13:11