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

dense and sparse graphs A dense graph has a large number of edges (gener-
ally quadratic). Typical graphs are not dense but are sparse. (529)
Dijkstra's algorithm An algorithm that is used to solve the positive-weighted,
shortest-path problem. (546)
directed acyclic graph (DAG) A type of directed graph having no cycles. (529)
directed graph A graph in which edges are ordered pairs of vertices. (528)
edge cost (weight) The third component of an edge that measures the cost of
traversing the edge. (528)
event-node graph A graph that consists of event vertices that correspond to the
completion of an activity and all its dependent activities. Edges show
what activity must be completed to advance from one vertex to the next.
The earliest completion time is the longest path. (560)
graph A set of vertices and a set of edges that connect the vertices. (528)
indegree The number of incoming edges of a vertex. (555)
negative-cost cycle A cycle whose cost is less than zero and makes most, if not
all, paths undefined because we can loop around the cycle arbitrarily
many times and obtain an arbitrarily small weighted path length. (552)
path A sequence of vertices connected by edges. (528)
path length The number of edges on a path. (528)
positive-cost cycle In a longest-path problem, the equivalent of a negative-cost
cycle in a shortest-path problem. (561)
simple path A path in which all vertices are distinct, except that the first and
last vertices can be the same. (529)
single-source algorithms Algorithms that compute the shortest paths from
some starting point to all vertices in a graph. (534)
slack time The amount of time that an activity can be delayed without delay-
ing overall completion. (562)
topological sort A process that orders vertices in a directed acyclic graph such
that if there is a path from u to v , then v appears after u in the ordering. A
graph that has a cycle cannot have a topological order. (555)
unweighted path length The number of edges on a path. (538)
weighted path length The sum of the edge costs on a path. (528)

common errors

A common error is failing to ensure that the input graph satisfies the req-
uisite conditions for the algorithm being used (i.e., acyclic or positive
weighted).

1.