Skip to main content

Chapter 12 Graph Algorithms

In previous chapters, we have encountered a few algorithms for problems involving discrete structures such as finding euler circuits (Chapter 5) or partitioning a poset into antichains (Chapter 6). This chapter begins a sequence of three chapters that focus on algorithms. In this chapter we explore two minimization problems for graphs in which we assign a weight to each edge of the graph. The first problem studied is determining a spanning tree of minimum weight. The second is of finding shortest paths from a root vertex to each other vertex in a directed graph.