7 - Graph algorithms

Summary

Introduction

In this chapter, we will be putting the results we proved in Chapter 6 to work. We will develop algorithms to solve a variety of optimization problems, all important in their own right.

The first is to minimize the cost of a network joining together several nodes. This can always be achieved by using what is called a ‘greedy algorithm’.

Another problem is to find the distance between any two nodes along a given network, say a road network. Two simple iterative algorithms exist for this problem. A related problem is to find the path of longest length between two vertices of an acyclic directed graph. This arises in certain types of sequencing problems, where the edges represent elapsed times. We shall see that one of our algorithms for shortest paths can easily be adapted to solve this problem.

A different type of problem is exemplified by the construction of a timetable, given simple compatibility constraints. We can model this by colouring the vertices of a graph, but the best we can achieve is a heuristic algorithm, not optimal but just reasonably efficient.

We should note that Warshall's algorithm can also be interpreted as a graphical algorithm to calculate strong components, but that was treated when we studied transitive closures.

Implementations of these algorithms in Modula-2 can be found in the appendices.