## Network flows: theory, algorithms, and applicationsBringing together the classic and the contemporary aspects of the field, this comprehensive introduction to network flows provides an integrative view of theory, algorithms, and applications. It offers in-depth and self-contained treatments of shortest path, maximum flow, and minimum cost flow problems, including a description of new and novel polynomial-time algorithms for these core models. For professionals working with network flows, optimization, and network programming. |

### From inside the book

Results 1-3 of 87

Page 145

Repeated Shortest Path Algorithm If the network has

can solve the all-pairs shortest path problem by applying any single-source

shortest path algorithm n times, considering each node as the source node once.

Repeated Shortest Path Algorithm If the network has

**nonnegative**arc lengths, wecan solve the all-pairs shortest path problem by applying any single-source

shortest path algorithm n times, considering each node as the source node once.

Page 192

Whereas the maximum flow problem with zero lower bounds always has a

feasible solution (since the zero flow is feasible), the problem with

lower bounds could be infeasible. For example, consider the maximum flow

problem ...

Whereas the maximum flow problem with zero lower bounds always has a

feasible solution (since the zero flow is feasible), the problem with

**nonnegative**lower bounds could be infeasible. For example, consider the maximum flow

problem ...

Page 803

A linear program is an optimization problem with a linear objective function, a set

of linear constraints, and a set of

underlying decision variables; that is, it is an optimization model of the form i ...

A linear program is an optimization problem with a linear objective function, a set

of linear constraints, and a set of

**nonnegativity**restrictions imposed upon theunderlying decision variables; that is, it is an optimization model of the form i ...

### What people are saying - Write a review

User Review - Flag as inappropriate

Approachable, powerful text.

### Contents

INTRODUCTION | 1 |

PATHS TREES AND CYCLES | 23 |

ALGORITHM DESIGN AND ANALYSIS | 53 |

Copyright | |

25 other sections not shown

### Other editions - View all

Network Flows Ravindra K. Ahuja,Sloan School of Management,Thomas L Magnanti No preview available - 2015 |

### Common terms and phrases

adjacency list algorithm performs Application arc costs arc flows arc i,j arc lengths augmenting path algorithm bipartite capacity scaling algorithm commodity constraints cost flow problem define denote Dijkstra's algorithm directed cycle directed network directed path discussion distance label example Exercise feasible flow feasible solution Fibonacci heap flow algorithms formulation implementation integer iteration label-correcting algorithm Lagrangian multiplier Lagrangian relaxation Lemma linear programming lower bound matching matrix maximum flow problem minimum cost flow minimum spanning tree multicommodity flow problem negative cycle network contains network flow problem network G network simplex algorithm node potentials nonnegative objective function value operation optimal solution optimality conditions path from node polynomial preflow-push algorithm reduced cost residual network s-t cut satisfies scaling phase Section shortest path distances shortest path problem Show shown in Figure simplex method sink node source node Suppose Theorem undirected units of flow upper bound variables zero