Java Reference
In-Depth Information
figure 14.5
Data structures used
in a shortest-path
calculation, with an
input graph taken
from a file; the
shortest weighted
path from
A
to
C
is
A
to
B
to
E
to
D
to
C
(cost is 76).
D C
A B
D B
A D
E D
B E
C A
10
12
23
87
43
11
19
12
A
B
11
87
19
23
C
D
E
10
43
Visual representation of graph
Input
66
D
10
23
76
C
19
D
C
A
B
E
0
A
12
87
12
B
11
vertexMap
23
E
43
Legend:
Dark-bordered boxes are
Vertex
objects. The unshaded portion in each box
contains the name and adjacency list and does not change when shortest-path computation
is performed. Each adjacency list entry contains an
Edge
that stores a reference to another
Vertex
object and the edge cost. Shaded portion is
dist
and
prev
, filled in after shortest path
computation runs.
Dark arrows emanate from
vertexMap
. Light arrows are adjacency list entries. Dashed arrows
are the
prev
data member that results from a shortest-path computation.
The second major data structure is the
Vertex
object that stores informa-
tion about all the vertices. Of particular interest is how it interacts with other
Vertex
objects. Figures 14.4 and 14.5 show that a
Vertex
object maintains four
pieces of information for each vertex.
name
: The name corresponding to this vertex is established when the
vertex is placed in the map and never changes. None of the shortest-
path algorithms examines this member. It is used only to print a final
path.
n
Search WWH ::
Custom Search