3
$\begingroup$

I have a simple directed graph $G(V,E)$ that has a source $s$ and sink $t$. Each edge $e$ of $G$ has positive integer capacity $c(e)$ and positive integer cost $a(e)$. I am trying to find the minimum cost maximum flow from $s$ to $t$ using the successive shortest path algorithm. It goes something like this:

Initialize all edge flows to 0.
Initialize all potentials pi[v] to 0.
While there exists an augmenting path in G_f (the residual network):
    Set the costs of all edges e = uv to be:
        b(e) = a(e) + pi[u] - pi[v], if e exists in G or
        b(e) = -a(e_reverse) + pi[u] - pi[v], where e_reverse = vu otherwise
    # We are now assured all edges have nonnegative costs
    Using Dijkstra method with costs b(e) in G_f:
        Find the cheapest augmenting path from s to t
        Calculate dist(v), the cost of cheapest path from s to v
    Augment the cheapest path to t to current flow
    Set pi[v] = pi[v] + dist(v) for all vertices v
The current flow gives the minimum cost maximum flow.

Obviously, if all costs $a(e) \le a_{max}$ and all capacities $c(e) \le c_{max}$, then there is a loose bound $|E|c_{max}a_{max}$ for cost of minimum cost maximum flow. However, the bounds on the potentials $\pi(v)$ and distances $dist(v)$ are not so obvious. In fact, judging by how the algorithm adds $dist(v)$ to $\pi(v)$ each iteration, $\pi(v)$ can possibly be multiplied by $|V|$ each iteration!

My question is, is there a way to calculate a non-exponential bound for $\pi(v)$? For instance, if all capacities and costs are at most $100$, $|V| = 200$, $|E| = 5000$, is it possible that $\pi(v)$ and $dist(v)$ still exceed 64-bit integers? How do so many implementations not use Big Integers?

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.