Max flow in simple weighted graph with no specified source or sink

Question

I am modeling a traffic network with a simple edge-weighted graph. The edge weights represent the capacity of each road. I would like to measure the maximum flow the network can accept.

In order to implement any kind of max-flow algorithm, I know part of the trick is changing each undirected weighted edge into a pair of directed edges with identical weights.

My problem is I do not have a specified source or sink for my network. The only thing I can think of is to try every possible pairing of distinct vertices as a source/sink pair, but that leaves me $10^{10}$ pairings to check, which is untenable.

Any other ideas on how to approach this?

Answer 1

I am not entirely sure, if I got your problem, but that's what I came up with:

I think you should try Minimum-Mean-Cycle-Cancelling Algorithm on a slightly modified graph:

Set costs to all edges in your network to $c(e)=0$. Add two vertices s,t to your Network. Add edges $(s,v)$ and $(v,t)$ $\forall v \in V(G)$ and $(t,s)$ and set the costs to $c((s,v))=c((v,t))=1$ and $c((t,s))=-3$. Capacity of the added edges should be $\infty$.

The mentioned algorithm searches for cycles in $G_f$ with minimum mean weight as long as there are negative weighted cycles in $G_f$ and augments along them. This is a special case of MIN-COST-FLOW-PROBLEM with $b\equiv 0$. Start the algorithm with $f\equiv 0$.