How I can write like an objective function subject to its corresponding restriccions the next problem?
(max "…")
subject to ($\sum "…" – \sum "…"=0$ $\forall$ "…")
I have a directed graph and I would like to find the maximum number of paths that there are between two nodes (source and destination) without repeating nodes.
Thanks in advance!
Best Answer
You can do this by considering the following oriented graph:
For every node $x$ of your graph, create nodes $x_1$ and $x_2$, with an arc from $x_1$ to $x_2$.
For every arc $(x,y)$ of your graph, create arcs $(x_2,y_1)$ and $(y_2,x_1)$ with a unit capacity. (You can delete arcs entering your source and leaving your destination, they are useless).
Your problem is now equivalent to finding a maximum flow (https://en.wikipedia.org/wiki/Maximum_flow_problem) between your source and destination (the maximum flow equals the maximum number of disjoint paths, and each flow will travel through one of the paths). Linear formulations of this problem are well known, see for example http://theory.stanford.edu/~trevisan/cs261/lecture15.pdf (first link on Google).