Java Reference
In-Depth Information
For
Path
, the comparison function compares the
cost
data member only. If
the
dest
data member is used to drive the comparison function, the algo-
rithm may appear to work for small graphs, but for larger graphs, it is
incorrect and gives slightly suboptimal answers. It never produces a path
that does not exist, however. Thus this error is difficult to track down.
2.
The shortest-path algorithm for negative-weighted graphs must have a
test for negative cycles; otherwise, it potentially runs forever.
3.
All the algorithms in this chapter are online in one file. The
Vertex
class has
an additional data member that is used in the alternative implementation of
Dijkstra's algorithm shown in Section 23.2.3.
Graph.java
Contains everything in one file with the simple
main
shown
in Figure 14.14.
IN SHORT
14.1
Find the shortest unweighted path from
V
3
to all others in the graph
shown in Figure 14.1.
Find the shortest weighted path from
V
2
to all others in the graph
shown in Figure 14.1.
14.2
Which algorithms in this chapter can be used to solve Figure 14.2?
14.3
In Figure 14.5, reverse the direction of edges (
D
,
C
) and (
E
,
D
). Show
the changes that result in the figure and the result of running the topo-
logical sorting algorithm.
14.4
Suppose that edges (
C
,
B
) with a cost of 11 and (
B
,
F
) with a cost of 10
are added to the end of the input in Figure 14.5. Show the changes
that result in the figure and recompute the shortest path emanating
from vertex
A
.
14.5
IN THEORY
14.6
Show how to avoid quadratic initialization inherent in adjacency
matrices while maintaining constant-time access of any edge.
Explain how to modify the unweighted shortest-path algorithm so
that, if there is more than one minimum path (in terms of number of
edges), the tie is broken in favor of the smallest total weight.
14.7
Search WWH ::
Custom Search