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?


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.