Java Reference
In-Depth Information
line for its turn. Also, as it clearly does not need to go before any other ver-
tices that have already had their distances lowered, w needs to be placed at
the end of a queue of vertices waiting for an eyeball visitation.
To select a vertex v for the eyeball, we merely choose the front vertex from
the queue. We start with an empty queue and then we enqueue the starting ver-
tex S . A vertex is enqueued and dequeued at most once per shortest-path calcu-
lation, and queue operations are constant time, so the cost of choosing the
vertex to select is only for the entire algorithm . Thus the cost of the
breadth-first search is dominated by the scans of the adjacency list and is
, or linear, in the size of the graph.
When a vertex has
its distance low-
ered (which can
happen only once),
it is placed on the
queue so that the
eyeball can visit it in
the future. The
starting vertex is
placed on the
queue when its dis-
tance is initialized to
zero.
OV
()
OE
()
14.2.2 java implementation
The unweighted shortest-path algorithm is implemented by the method
unweighted , as shown in Figure 14.22. The code is a line-for-line translation of
the algorithm described previously. The initialization at lines 6-13 makes all
the distances infinity, sets D S to 0, and then enqueues the start vertex. The
queue is declared at line 12. While the queue is not empty, there are vertices to
visit. Thus at line 17 we move to the vertex v that is at the front of the queue.
Line 19 iterates over the adjacency list and produces all the w 's that are adja-
cent to v . The test D w =
Implementation is
much simpler than
it sounds. It follows
the algorithm
description verba-
tim.
is performed at line 23. If it returns true , the update
D w = D v + 1 is performed at line 25 along with the update of w 's prev data
member and enqueueing of w at lines 26 and 27, respectively.
positive-weighted,
shortest-path problem
14.3
Recall that the weighted path length of a path is the sum of the edge costs on
the path. In this section we consider the problem of finding the weighted
shortest path, in a graph whose edges have nonnegative cost. We want to find
the shortest weighted path from some starting vertex to all vertices. As we
show shortly, the assumption that edge costs are nonnegative is important
because it allows a relatively efficient algorithm. The method used to solve the
positive-weighted, shortest-path problem is known as Dijkstra's algorithm. In
the next section we examine a slower algorithm that works even if there are
negative edge costs.
The weighted path
length is the sum of
the edge costs on a
path.
positive-weighted, single-source, shortest-path problem
Find the shortest path (measured by total cost) from a designated vertex S to
every vertex. All edge costs are nonnegative.
 
 
Search WWH ::




Custom Search