Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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,


share|cite|improve this question
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
This is a special case of Steiner tree problem which is without additional constraints NP-complete. – dtldarek Apr 17 '12 at 7:42
@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
Is this homework? – 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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.