# Linear programming formulation of cheapest k-edge path between two nodes

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.

• 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. Jan 14, 2015 at 22:08
• 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?)
– D.W.
Jan 14, 2015 at 22:14

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))$.