• Start with flow f with f ( u,v )=0 for all u , v . • repeat until value( f ) = r – Find the shortest path P in G f from s to t – Let q be the minimum residual capacity of an edge on P. – Send min( q , r – value( f )) additional units of flow across P. On the successive shortest paths algorithm : • May use exponential running time • Assume G has no negative edge costs. • Gives optimal answer. – Invariant: f has minimum cost among all flows with value value ( f ). • Suppose we obtain f’ from f by sending across P. • Let f’’ be a minimum cost flow with same value as f’ . • Write f’’ – f as weighted sum of paths from s to t in G f and circuits in G f . Argue that cost( f’ – f ) / cost( f’’ – f ), using that: – P is shortest path – Circuits have non-negative costs, by optimality of f . Source code link is given here
Network programming and scalable micro-services in Azure