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
    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}$.2012-04-17
  • 0
    This is a special case of [Steiner tree problem](http://en.wikipedia.org/wiki/Steiner_tree_problem) which is without additional constraints NP-complete.2012-04-17
  • 0
    @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.)2012-04-17
  • 0
    Is this homework?2012-04-17
  • 0
    @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.2012-04-17
  • 0
    By the way. This is not homework. I'm working as an IT consultant in logistics. This is a problem we face.2012-04-17
  • 0
    "Note that if two paths use the same vertex $v_i$, the cost $C$ is only paid once." — This makes things complicated. If every path paid for every vertex it traversed, you could just replace each vertex $v$ with a directed edge $v^- \mathord\to v^+$ with cost $C$, and then replace every edge $u \mathord\to v$ with the corresponding edge $u^+ \mathord\to v^-$.2012-04-17
  • 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