<p>I assume you are given an undirected network $G$, and two vertices $s,t$, and you wish to maximize the flow from $s$ to $t$, while directing the edges of $G$. In this case, you can just use the normal Ford-Fulkerson algorithm with the following modification:</p>

<p>Every time you take an augmenting $s$-$t$ path in $G$ and send flow along it, direct the edges along the path. Eventually, your algorithm will stop, and all edges (except those with flow 0) will have a direction. The flow will be maximal, which can be proven using the max-flow-min-cut theorem.</p>

CC BY-SA 3.0
2012-04-27T10:56:43.883Z
2012-04-27T10:56:43.883Z
utdiscant
<p>One of the most amazing theorems in graph theory is Nash-William's :</p>

<p><a href="http://en.wikipedia.org/wiki/Strong_orientation" rel="nofollow">http://en.wikipedia.org/wiki/Strong_orientation</a></p>

<p>.... And its proof is constructive, but not that easy to implement :-)</p>

CC BY-SA 3.0
2012-04-27T08:14:10.467Z
2012-04-27T08:14:10.467Z
Nathann Cohen
<p>Is there any algorithm that can orient undirected graph G(V,E) (i.e., assign directions to edges) to achieve maximum flow in the network? Any suggestion?</p>

<ds.algorithms><graph-theory>
Max-Flow and Graph Orientation:
Waleed
# Max-Flow and Graph Orientation:

(Asked by: username_0 on 2012-04-27)

Is there any algorithm that can orient undirected graph G(V,E) (i.e., assign directions to edges) to achieve maximum flow in the network? Any suggestion?

**Tags:** ds.algorithms, graph-theory


---

## 2 answers

### Answer by username_1 on 2012-04-27. Score: 3

I assume you are given an undirected network $G$, and two vertices $s,t$, and you wish to maximize the flow from $s$ to $t$, while directing the edges of $G$. In this case, you can just use the normal Ford-Fulkerson algorithm with the following modification:

Every time you take an augmenting $s$-$t$ path in $G$ and send flow along it, direct the edges along the path. Eventually, your algorithm will stop, and all edges (except those with flow 0) will have a direction. The flow will be maximal, which can be proven using the max-flow-min-cut theorem.


---

### Answer by username_2 on 2012-04-27. Score: 2

One of the most amazing theorems in graph theory is Nash-William's :

<http://en.wikipedia.org/wiki/Strong_orientation>

.... And its proof is constructive, but not that easy to implement :-)


---

