Java Reference
In-Depth Information
figure 14.38
Worst-case running
times of various graph
algorithms
Type of Graph Problem
Running Time
Comments
O
()
Unweighted
Breadth-first search
Weighted, no negative edges
OE V
(
log
)
Dijkstra's algorithm
OE V
(
⋅
)
Weighted, negative edges
Bellman-Ford algorithm
Weighted, acyclic
O
()
Uses topological sort
sparse, so choosing appropriate data structures to implement them is
important.
For unweighted graphs, the shortest path can be computed in linear
time, using breadth-first search. For positive-weighted graphs, slightly more
time is needed, using Dijkstra's algorithm and an efficient priority queue.
For negative-weighted graphs, the problem becomes more difficult. Finally,
for acyclic graphs, the running time reverts to linear time with the aid of a
topological sort.
Figure 14.38 summarizes those characteristics for these algorithms.
activity-node graph
A graph of vertices as activities and edges as precedence
relationships. (560)
adjacency lists
An array of lists used to represent a graph, using linear space.
(530)
adjacency matrix
A matrix representation of a graph that uses quadratic space.
(530)
adjacent vertices
Vertex
w
is adjacent to vertex
v
if there is an edge from
v
to
w
. (528)
Bellman-Ford algorithm
An algorithm that is used to solve the negative-
weighted, shortest-path problem. (553)
breadth-first search
A search procedure that processes vertices in layers:
Those closest to the start are evaluated first, and those most distant are
evaluated last. (542)
critical-path analysis
A form of analysis used to schedule tasks associated with
a project. (560)
cycle
In a directed graph, a path that begins and ends at the same vertex and
contains at least one edge. (529)
Search WWH ::
Custom Search