Search
Next: 0.4.1 Graph Representation Up: Algorithm Archive (Work in Previous: 0.3.10.3 Source Code

# 0.4 Graph Algorithms

A graph is a finite set of vertices and edges. Each edge in a graph must begin and end at a different vertex (and, thus, no edges can "loop" joining one vertex to itself). Moreover between any pair of vertices there can be only one edge. Vertices are sometimes also called nodes. Nodes joined by an edge are said to be adjacent.

We call moving between vertices along edges traversing a graph.

In directed graphs, or di-graphs, every edge has orientation.       It is only possible to traverse a given edge in one direction. All edges are like one-way streets; traffic can only flow in a single direction.

In weighted graphs, each edge has a cost associated with     it. To move from a pair of vertices with an edge joining them you have to pay a toll - the price of that edge. It is often possible, however, to circumvent expensive edges by finding a less expensive, more indirect route, between an edge's endpoints. In the following section we will explore several algorithms designed to find the shortest path between two vertices.

Scott Gasch
1999-07-09