Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|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

 
discard

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

Browse other questions tagged or ask your own question.