Java Reference
In-Depth Information
T
1
10
3
cost
5
9
5
8
6
0
5
10
15
108
2
0123456
8
8
6
4
parent
1
2
-1
1
1
5
0
0
2
7
5
0123456
0
4
5
(a)
(b)
F
IGURE
29.18
Now vertices {
1
,
2
,
6
,
0
,
3
,
5
,
4
} are in set
T
.
AbstractGraph.Tree
WeightedGraph.ShortestPathTree
-cost: int[]
cost[v]
stores the cost for the path from the source to
v
.
+ShortestPathTree(source: int, parent: int[],
searchOrder: List<Integer>, cost: int[])
+getCost(v: int): int
+printAllPaths(): void
Constructs a shortest path tree with the specified
source
,
parent
array,
searchOrder
, and
cost
array.
Returns the cost for the path from the source to vertex
v
.
Displays all paths from the source.
F
IGURE
29.19
WeightedGraph.ShortestPathTree
extends
AbstractGraph.Tree
.
infinity for all other vertices (lines 159-161). The parent of
sourceVertex
is set to
-1
(line 166).
T
is a list that stores the vertices added into the shortest path tree (line 169). We use
a list for
T
rather than a set in order to record the order of the vertices added to
T
.
Initially,
T
is empty. To expand
T
, the method performs the following operations:
1. Find the vertex
u
with the smallest
cost[u]
(lines 175-181) and add it into
T
(line 183).
2. After adding
u
in
T
, update
cost[v]
and
parent[v]
for each
v
adjacent to
u
in
V-T
if
cost[v] > cost[u] + w(u, v)
(lines 186-192).
Once all vertices from
s
are added to
T
, an instance of
ShortestPathTree
is created
(line 196).
The
ShortestPathTree
class extends the
Tree
class (line 200). To create an instance
of
ShortestPathTree
, pass
sourceVertex
,
parent
,
T
, and
cost
(lines 204-205).
sourceVertex
becomes the root in the tree. The data fields
root
,
parent
, and
searchOrder
are defined in the
Tree
class, which is an inner class defined in
AbstractGraph
.
Note that testing whether a vertex
i
is in
T
by invoking
T.conatins(i)
takes
O(n)
time,
since
T
is a list. Therefore, the overall time complexity for this implemention is
O
(
n
3
). Inter-
ested readers may see Programming Exercise 29.20 for improving the implementation and
reducing the complexity to
O
(
n
2
).
Dijkstra's algorithm is a combination of a greedy algorithm and dynamic programming. It
is a greedy algorithm in the sense that it always adds a new vertex that has the shortest distance
to the source. It stores the shortest distance of each known vertex to the source and uses it
later to avoid redundant computing, so Dijkstra's algorithm also uses dynamic programming.
ShortestPathTree
class
Dijkstra's algorithm time
complexity
greedy and dynamic
programming
Search WWH ::
Custom Search