Graphs and paths - Data Structures and Problem Solving Using Java - page 527

chapter 14

graphs and paths

I n this chapter we examine the graph and show how to solve a particular
kind of problem—namely, calculation of shortest paths. The computation of
shortest paths is a fundamental application in computer science because many
interesting situations can be modeled by a graph. Finding the fastest routes for
a mass transportation system, and routing electronic mail through a network
of computers are but a few examples. We examine variations of the shortest
path problems that depend on an interpretation of shortest and the graph's
properties. Shortest-path problems are interesting because, although the algo-
rithms are fairly simple, they are slow for large graphs unless careful attention
is paid to the choice of data structures.
In this chapter, we show

Formal definitions of a graph and its components

n

The data structures used to represent a graph

n

Algorithms for solving several variations of the shortest-path problem,
with complete Java implementations

n