Network Optimization

Optimization · Axiom Academy

Solving optimization problems on graphs: flows, paths, and the structure of network problems A flow network is a directed graph G = (V, E) where each edge (i,j) has a capacity c ij that limits how much flow can pass through it. We often have a source node s where flow originates and a sink node t where flow terminates. The animation shows a simple network with capacities on edges. Flow must satisfy two key constraints: capacity constraints (flow cannot exceed edge capacity) and flow conservation (flow in equals flow out at intermediate nodes). 2. Shortest Path and Maximum Flow Shortest Path Problem: Find the path from source to sink that minimizes total edge costs. Algorithms like Dijkstra's and Bellman-Ford solve this efficiently. Maximum Flow Problem: Send as much flow as possible from source s to sink t while respecting capacity constraints. The Ford-Fulkerson algorithm finds augmenting paths to increase flow until no improvement is possible. The animation demonstrates finding an augmenting path and pushing flow through it to increase the total flow. The minimum cost flow problem combines flow amounts with edge costs. Each edge has both a capacity c ij and a cost per unit flow a ij . We want to send a specified amount of flow from source to sink while minimizing total cost. This generalizes both shortest path (send 1 unit at minimum cost) and max flow (ignore costs, maximize amount sent). The network simplex algorithm efficiently solves min cost flow problems.

This is the written version of the interactive lesson above. See the full Optimization course.