I'm trying to design an algorithm for the following optimization problem. Suppose that $G=(V, E)$ is a digraph where $V$ and $E$ are sets of vertices and edges of $G$, respectively. $|V| = n$ and $|E| = m$. $c$ is the cost vector; $c_{ij}$ is the cost of edge $(i,j)$. Costs can be negative and $G$ may have cycles (negative or positive). The target is a minimum cost flow from source vertex $1$ to sink vertex $n$ which must satisfy some constraints. So let $x$ be the solution vector; if $x_{ij}=1$ then the edge $(i,j)$ is a part of minimum cost flow. Here is my optimization problem:
$$min \sum_{(i,j)\in E}c_{ij}x_{ij}$$
Subject to these constraints:
$$\begin{array}{ll} \sum_{i\in V}x_{ij}&=&\sum_{i\in V}x_{ji}~~~~~~\forall j\in V (j\neq1,n)\\ \sum_{j\in V}x_{1j}&=&1\\ \sum_{i\in V}x_{in}&=&1\\ x_{ij}&\in&\{0,1\}~~~~~~\forall i,j\in V\end{array}$$
First constraint makes us sure that in the final solution vector, total number of edges outgoing from vertex $i$ and total number of edges incoming to that vertex are equal.
Only one edge can go out from vertex $1$, based on second constraint and only one edge can come to vertex $n$, based on third constraint.
Finally, last constraint tells us that the maximum flow allowed for each edge is $1$.
This is the problem of sending a flow of value one from vertex $1$ to vertex $n$ subject to the constraints with a capacity limit of $1$ on each edge and the vector $b$ set to $0$.
I asked this question because I think a flow in this case can be viewed as a path, in which we can goes around it's cycles (if any cycle exists on the path) only once and it can't meet vertices $1$ and $n$ more than once. So, can we solve this problem using a modified version of Bellman-Ford or any other dynamic programming algorithm? Time order isn't the matter to me. I just don't want to use algorithms designed for the general form of minimum cost flow problem.
