6.3. Simplifying the Network*

The algorithms in this chapter—yes, we are almost ready to finally talk about algorithms again—either crucially depend on the input network satisfying certain conditions or are at least easier to describe or implement if the network satisfies these conditions. For example, we may require that all edges have non-negative costs or that all edges have infinite capacity. In this section, we show that this does not restrict the applicability of these algorithms because any network can be converted into an equivalent one that meets these requirements.