6. Directed Graphs

This chapter gives a number of algorithms that apply to directed graphs, though many ideas and algorithms for undirected graphs apply to digraphs (and vice versa). The first is an algorithm to orient the edges of an undirected graph to produce a strongly-connected digraph. Then we consider acyclic digraphs, showing how they may be “topologically sorted”, and how to use Dynamic Programming to count the number of dipaths from a to b, and find a shortest or a longest dipath from a to b. Dijkstra’s Algorithm grows a tree of shortest dipaths from a “single source”, and the Floyd-Warshall Algorithm solves the “all-pairs” shortest dipath problem. Next we consider commodity Flow Networks. The Max-flow/Min-cut Theorem is proved by the action of the Ford-Fulkerson algorithm which finds a feasible flow, and gives it a “certificate of optimality” by producing a cut whose capacity equals the value of that flow. The final section shows that matching problems in bipartite graphs can be converted to flow problems and proves several classic results, including Hall’s Marriage Theorem.