3
$\begingroup$

Given a directed graph $G = (V,E)$ with positive edge weights, find the minimum cost path between $s$ and $t$ that traverses exactly $k$ edges.

Here is my attempt using a flow network: \begin{align} \min \sum_{(i,j) \in E} c_{ij}x_{ij} \end{align} \begin{align} \sum_{j \in V} x_{ji} - \sum_{j \in V} x_{ij} &= \begin{cases} -1,& \text{if } i = s\\ 1, & \text{if } i = t\\ 0, & \text{otherwise}\\ \end{cases} && \forall i \in V\\ \sum_{(i,j) \in E} x_{ij} &= k &&\\ x_{ij} &\geq 0 && \forall (i,j) \in E\\ \end{align}

However, this doesn't eliminate cycles which are disjoint from the $s$-$t$ path. I can use subtour elimination constraints like in the Miller Tucker Zemlin formulation of the Travelling Salesman Problem but this enforces a simple path making the problem harder than it should be.

Any ideas on alternative formulations?

Update: This is part of a slightly bigger formulation here, where $z$ is a slack variable which scalarizes multiple objectives with a rectified-linear function:

\begin{align} \min \sum_{k \in K} z_{k} \end{align} \begin{align} \sum_{(i,j) \in E} c^{k}_{ij}x_{ij} - z_{k} &\leq 1 && \forall k \in K\\ \sum_{j \in V} x_{ji} - \sum_{j \in V} x_{ij} &= \begin{cases} -1,& \text{if } i = s\\ 1, & \text{if } i = t\\ 0, & \text{otherwise}\\ \end{cases} && \forall i \in V\\ x_{ij} &\geq 0 && \forall (i,j) \in E\\ \end{align}

Solutions are integral when solving with a linear program, but suggestions for more efficient algorithms would be appreciated.

$\endgroup$
  • $\begingroup$ Edited for clarity. Regarding your first question, I have a nonlinear objective and additional constraints that make this a problem that can't be easily solved with BFS. So I'd like to understand the simpler problem's formulation. $\endgroup$ – bravetang8 Jan 14 '15 at 22:08
  • 1
    $\begingroup$ So you would consider solutions that don't use network flow/linear programming unacceptable? There are other approaches to the original problem that don't involve network flow and are quite reasonable. Are they unacceptable/unhelpful to you? If so, you should edit the question further to clarify the requirements on what would count as an answer you'd consider acceptable. (Perhaps you might like to add some kind of comments on the general nature of your objective and/or other constraints?) $\endgroup$ – D.W. Jan 14 '15 at 22:14
2
$\begingroup$

The simplest way to compute the shortest path from $s$ to $t$ that traverses exactly $k$ edges is by increasing the size of the graph $k$-fold.

In particular, make $k$ copies of the vertices and $k-1$ copies of the edges, where for each edge $(u,v)$ in the original graph, we add an edge from the $i$th copy of $u$ to the $i+1$th copy of $v$ (for all $i$). Now look for the shortest path from the 1st copy of $s$ to the $k$th copy of $t$ using a standard algorithm (e.g., Dijkstra's algorithm). The running time will be $O(kn+km\lg(kn))$.

Only you can determine whether this kind of formulation will be compatible with your additional constraints and objective function (since you haven't told us what they are), but this kind of modification to the graph is a general approach for this sort of problem that is pretty flexible and might meet your needs.

You could presumably also combine this with your network flow / LP formulation. Now there will be no cycles that can show up, as the resulting graph is acyclic (a dag). I don't know if that will meet your needs.

$\endgroup$
  • $\begingroup$ Thanks for your answer, it makes sense to make feasible paths explicit in the graph in this way. Do you have any resources or references? I updated with the additional constraints- which are no longer nonlinear as I stated before. I'd still be interested in any solutions that don't use linear programming. $\endgroup$ – bravetang8 Jan 15 '15 at 18:17
  • $\begingroup$ @bravetang8, it's a standard technique, so I don't have any references. I added one more paragraph to my answer to elaborate on another way you could use this sort of construction. $\endgroup$ – D.W. Jan 15 '15 at 19:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.