ABSTRACT
This chapter focuses on some of the basic ideas used in network algorithms. It introduces the residual digraph, which is central to the maximum flow and minimum cost-maximum flow algorithms. The chapter shows that a digraph can be topologically ordered if it contains no order cycles. It describes an algorithm to solve it and apply the algorithm to an example. Shortest Path Algorithm applies to both graphs and digraphs. It is similar to the longest path algorithm, but it differs in that the whole scanning order is not known when the algorithm begins: the node to be scanned at step n + 1 is determined during step n. A model digraph for a project planning problem is a NOcycle, topologically ordered digraph.
