Unlock document.
This document is partially blurred.
Unlock all pages and 1 million more documents.
Get Access
12.15 If there is a negative cycle, then after the nth pass some edge uu1 will be relaxed,
12.16 Consider the input the input graph consists of a path, i.e., having edges set E =
12.17 The following is the trace of Dijkstra’s algorithm generating a shortest path
spanning tree with root vertex r = 2 for the given digraph.
Stage I
i
0
1
2
3
4
5
Dist[i]
13
0
3
9
Parent[i]
-
2
-1
2
-
2
InTheTree[i]
F
F
T
F
F
F
Stage II
i
0
1
2
3
4
5
Dist[i]
13
0
3
4
9
Parent[i]
-
2
-1
2
3
2
InTheTree[i]
F
F
T
T
F
F
Stage III
i
0
1
2
3
4
5
Dist[i]
13
0
3
4
8
Parent[i]
-
2
-1
2
3
4
InTheTree[i]
F
F
T
T
T
F
Stage IV
i
0
1
2
3
4
5
Dist[i]
9
13
0
3
4
8
Parent[i]
5
3
-1
2
3
4
InTheTree[i]
F
F
T
T
T
T
Stage V
i
0
1
2
3
4
5
Dist[i]
9
12
0
3
4
8
Parent[i]
5
0
-1
2
3
4
InTheTree[i]
T
F
T
T
T
T
The algorithm now terminates, since vertex 2 is added without any additional work.
12.18 a) The following is the trace of Dijkstra’s algorithm for the graph of Figure 12.5
with root vertex r = 0.
Stage I
i
0
1
2
3
4
5
Dist[i]
0
6
1
Parent[i]
-1
0
-
-
-
0
InTheTree[i]
T
F
F
F
F
F
Stage II
i
0
1
2
3
4
5
Dist[i]
0
4
12
7
1
Parent[i]
-1
5
5
-
5
0
InTheTree[i]
T
F
F
F
F
T
Stage III
i
0
1
2
3
4
5
Dist[i]
0
4
12
7
1
Parent[i]
-1
5
5
-
5
0
InTheTree[i]
T
T
F
F
F
T
Stage IV
i
0
1
2
3
4
5
Dist[i]
0
4
10
7
1
Parent[i]
-1
5
4
4
5
0
InTheTree[i]
T
T
F
F
T
T
Stage V
i
0
1
2
3
4
5
Dist[i]
0
4
10
7
1
Parent[i]
-1
5
4
4
5
0
InTheTree[i]
T
T
F
T
T
T
distinct weights to the edges: edge {0, i} has weight i, i = 1,2,...,n – 1, and edge {i,
i+1} has weight 1+1/i, i = 1,2,...,n – 2.
Letting r = 0, it is easy to see that the shortest path spanning tree rooted at r consists of
the edge {0,1}, together with the edges {i,i+1}, i = 1,2,...,n – 2. On the other hand, the
12.19
Stage 1
The algorithm now terminates, since vertex 3 is added
without any additional work.
two edges {a,b} and {a,c} having weights 2 and 1,
respectively.
tree generated by Dijkstra’s algorithm for root vertex
12.22 We implement Dijkstra’s algorithm using a priority queue whose operations
include the operation of changing the priority value of an element as well as the usual
operations of enqueue and dequeue
procedure Dijkstra(G,w,Parent[0:n – 1])
Input: G (a connected graph with vertex set V and edge set E)
i
0
1
2
3
4
5
6
7
Dist[i]
4
0
7
∞
∞
3
∞
9
Parent[i]
1
-1
1
-
-
1
-
1
i
0
1
2
3
4
5
6
7
Dist[i]
4
0
7
∞
9
3
5
7
Parent[i]
1
-1
1
-
5
1
5
0
InTheTree[i]
T
T
F
F
F
T
T
F
i
0
1
2
3
4
5
6
7
InTheTree[i]
T
T
T
F
F
T
T
F
i
0
1
2
3
4
5
6
7
Dist[i]
4
0
7
11
9
3
5
7
Parent[i]
1
-1
1
4
5
1
5
0
3
2
7
2
7
2
7
3
min-heap, where the priority of vertex v is initialized to priority(v) = w(rv) if rv is
an edge of G and priority(v) = ∞, otherwise
for Stage ← 1 to n – 1 do
dequeue vertex u //u has the highest priority value, i.e., the smallest value, of all
// the elements in Q
12.23 Consider the dag D on vertex set V = {0,1,2} with edge set E = {(0,1),(0,2),(2,1)}
where edge (0,1) has weight 2, edge (0,2) has weight 3, and edge (2,1) has weight -2.
Dijkstra’s algorithm generates the tree having edges (0,1) and (0,2), yielding the path
12.24 Since the matrices for Floyd’s algorithm for a graph is symmetric, we only show
the upper triangular portions of these matrices.
S-1:
0
1
2
3
4
5
6
0
0
9
∞
∞
∞
1
∞
1
0
1
∞
∞
8
2
2
0
10
1
∞
2
3
0
4
∞
∞
4
0
6
∞
5
0
4
6
0
S0:
0
1
2
3
4
5
6
0
0
9
∞
∞
∞
1
∞
1
0
1
∞
∞
8
2
2
0
10
1
∞
2
3
0
4
∞
∞
4
0
6
∞
5
0
4
6
0
P0:
0
1
2
3
4
5
6
0
-1
-1
-1
-1
-1
-1
-1
1
-1
-1
-1
-1
-1
-1
2
-1
-1
-1
-1
-1
3
-1
-1
-1
-1
4
-1
-1
-1
5
-1
-1
6
-1
S1:
0
1
2
3
4
5
6
0
0
9
10
∞
∞
1
11
1
0
1
∞
∞
8
2
2
0
10
1
9
2
3
0
4
∞
∞
4
0
6
∞
5
0
4
6
0
P1:
0
1
2
3
4
5
6
0
-1
-1
1
-1
-1
-1
1
1
-1
-1
-1
-1
-1
-1
2
-1
-1
-1
1
-1
3
-1
-1
-1
-1
4
-1
-1
-1
5
-1
-1
0
1
2
3
4
5
6
0
0
9
10
20
11
1
11
1
0
1
11
2
8
2
2
0
10
1
9
2
0
1
2
3
4
5
6
0
-1
-1
1
2
2
-1
1
1
-1
-1
2
2
-1
-1
2
-1
-1
-1
1
-1
3
0
4
19
12
4
0
6
3
5
0
4
6
0
3
-1
-1
2
2
4
-1
-1
2
5
-1
-1
6
-1
S3:
0
1
2
3
4
5
6
0
0
9
10
20
11
1
11
1
0
1
11
2
8
2
2
0
10
1
9
2
3
0
4
19
12
4
0
6
3
5
0
4
6
0
P3:
0
1
2
3
4
5
6
0
-1
-1
1
2
2
-1
0
1
-1
-1
2
2
-1
-1
2
-1
-1
-1
1
-1
3
-1
-1
2
2
4
-1
-1
2
5
-1
-1
6
-1
S4:
0
1
2
3
4
5
6
0
0
9
10
15
11
1
11
1
0
1
6
2
8
2
2
0
5
1
9
2
3
0
4
10
7
4
0
6
3
5
0
4
6
0
P4:
0
1
2
3
4
5
6
0
-1
-1
1
4
2
-1
1
1
-1
-1
4
2
-1
-1
2
-1
4
-1
1
-1
3
-1
-1
4
4
4
-1
-1
2
5
-1
-1
6
-1
S5:
0
0
9
8
11
7
1
5
1
0
1
6
2
8
2
2
0
5
1
9
2
3
0
4
10
7
4
0
6
3
P5:
0
1
2
3
4
5
6
0
-1
-1
5
5
5
-1
5
1
-1
-1
3
2
-1
-1
2
-1
3
-1
1
-1
3
-1
-1
3
3
4
-1
-1
2
5
0
4
6
0
5
-1
-1
6
-1
S6:
0
1
2
3
4
5
6
0
0
7
7
11
7
1
5
1
0
1
6
2
6
2
2
0
5
1
6
2
3
0
4
10
7
4
0
6
3
5
0
4
6
0
P6:
0
1
2
3
4
5
6
0
-1
6
6
5
5
-1
5
1
-1
-1
3
2
6
-1
2
-1
3
-1
6
-1
3
-1
-1
3
3
4
-1
-1
2
5
-1
-1
6
-1
S-1:
0
1
2
3
4
5
0
0
∞
-2
∞
∞
∞
1
3
0
∞
∞
∞
∞
2
∞
4
0
∞
1
3
3
∞
∞
-1
0
1
∞
4
∞
∞
∞
2
0
1
5
4
∞
4
∞
∞
0
S0:
0
0
∞
-2
∞
∞
∞
1
3
0
1
∞
∞
∞
2
∞
4
0
∞
1
3
5
4
∞
2
∞
∞
0
P0:
0
-1
-1
-1
-1
-1
-1
1
-1
-1
0
-1
-1
-1
2
-1
-1
-1
-1
-1
-1
5
-1
-1
0
-1
-1
-1
S1:
0
1
2
3
4
5
0
0
∞
-2
∞
∞
∞
1
3
0
1
∞
∞
∞
2
7
4
0
∞
1
3
3
∞
∞
-1
0
1
∞
4
∞
∞
∞
2
0
1
5
4
∞
2
∞
∞
0
P1:
0
1
2
3
4
5
0
-1
-1
-1
-1
-1
-1
1
-1
-1
0
-1
-1
-1
2
1
-1
-1
-1
-1
-1
3
-1
-1
-1
-1
-1
-1
4
-1
-1
-1
-1
-1
-1
5
-1
-1
0
-1
-1
-1
S2:
0
1
2
3
4
5
0
0
2
-2
∞
-1
1
1
3
0
1
∞
2
4
2
7
4
0
∞
1
3
3
6
3
-1
0
0
2
4
∞
∞
∞
2
0
1
5
4
8
2
∞
3
0
P2:
0
1
2
3
4
5
0
-1
2
-1
-1
2
2
1
-1
-1
0
-1
2
2
2
1
-1
-1
-1
-1
-1
3
2
2
-1
-1
2
2
4
-1
-1
-1
-1
-1
-1
5
-1
2
0
-1
2
-1
S3:
0
1
2
3
4
5
0
0
2
-2
∞
-1
1
1
3
0
1
∞
2
4
2
7
4
0
∞
1
3
3
6
3
-1
0
0
2
4
8
5
1
2
0
1
5
4
8
2
∞
3
0
P3:
0
1
2
3
4
5
0
-1
2
-1
-1
2
2
1
-1
-1
0
-1
2
2
2
1
-1
-1
-1
-1
-1
3
2
2
-1
-1
2
2
4
3
3
3
-1
-1
-1
5
-1
2
0
-1
2
-1
S4:
0
1
2
3
4
5
0
0
2
-2
1
-1
0
2
7
4
0
3
1
2
4
8
5
1
2
0
1
5
4
8
2
7
3
0
P4:
0
1
2
3
4
5
0
-1
2
-1
4
2
4
2
1
-1
-1
4
-1
4
4
3
3
3
-1
-1
-1
5
-1
2
0
4
2
-1
S5:
0
1
2
3
4
5
0
0
2
-2
1
-1
0
1
3
0
1
4
2
3
2
7
4
0
3
1
2
3
6
3
-1
0
0
1
4
5
5
1
2
0
1
5
4
8
2
7
3
0
P5:
0
1
2
3
4
5
0
-1
2
-1
4
2
4
1
-1
-1
0
4
2
2
2
1
-1
-1
4
-1
4
3
2
2
-1
-1
2
2
4
5
3
3
-1
-1
-1
5
-1
2
0
4
2
-1
We can use P5 to determine the shortest path from vertex 1 to vertex 3 as follows:
P5 [1,3] = 4, so we know we must visit vertex 4 along the way. We then check to see
how to get from vertex 1 to 4, and from 4 to 3. Checking P5 [1,4] we see that we must
visit vertex 2 to travel from vertex 1 to 4 via the shortest path. By checking P5 [4,3], we
see that no intermediate vertices are required, so they must be adjacent.
We must then check to see how to travel from vertex 1 to vertex 2, and from 2 to 4.
Checking P5 [1,2] we see that we must visit vertex 0 to travel from vertex 1 to 2. By
12.26 The following recursive function InternalVertices outputs the internal vertices of
a shortest path from i to j in the order they occur in the path.
procedure InternalVertices(P[0:n – 1, 0:n – 1], i , j) recursive
Input: P[0:n – 1, 0:n – 1] (2-dimensional array generated by Floyd’s algorithm)
4
5
2
4
3
5
2
12.27
procedure ShortestPaths(P[0:n – 1, 0:n – 1], i , j) recursive
12.28 It is sufficient to show that Formula (12.2.1) hold with negative weight but no
negative cycles. Equivalently, it is sufficient to show that if P is a shortest path from i
to j whose internal vertices lie in {0, …, k} that contains k, then the subpath P1 from i
12.29 For an unweighted dag G assign each edge the weight -1 and apply Floyd’s
algorithms. The shortest paths generated with respect to this weighting correspond to
4
3
2
