24.

SINGLE SOURCE SHORTEST PATH

a. Exercise 24.1
-

Run the Bellman-Ford algorithm on the directed graph of Figure 24.4, using vertex z as the
source. In each pass, relax edges in the same order as in the figure, and show the d and
values after each pass. Now, change the weight of edge (z, x) to 4 and run the algorithm again,
using s as the source.

Prove Corollary 24.3.

Given a weighted, directed graph G = (V, E) with no negative-weight cycles, let m be the

Modify the Bellman-Ford algorithm so that it sets d[v] to - for all vertices v for which there is a

maximum over all pairs of vertices u, v V of the minimum number of edges in a shortest path
from u to v. (Here, the shortest path is by weight, not the number of edges.) Suggest a simple
change to the Bellman-Ford algorithm that allows it to terminate in m + 1 passes, even if m is not
known in advance.
We can simply implement this optimization of BELLMAN-FORD algorithm by
remebering if v was relaxed or not. If v isrelaxed then we wait to see
if v was udpated (which means being relaxed again). If v was not updated, then we
would stop.
Because the greatest number of edges on any shortest path from the source is m,
then the path-relaxation property tells us that after m iterations of BELLMAN-FORD,
every vertex v has achieved its shortest-path weight in v.d. By the upper-bound
property, after m iterations, no d values will ever change. Therefore, no d values will
change in the (m+1)st iteration. Because we do not know m in advance, we cannot
make the algorithm iterate exactly m times and then terminate. But if we just make the
algorithm stop when nothing changes any more, it will stop after m + 1 iterations.

negative-weight cycle on some path from the source to v.

Let G = (V, E) be a weighted, directed graph with weight function w : E R. Give an O(V E)time algorithm to find, for each vertex v V , the value *(v) = min{uV} {(u, v)}.

Suppose a graph G is not a weight of negative loop.

RELAX amend as follows:

That is the source point to consider u or u is a node on the

shortest path to the other two cases updates vd.
Then run the modified Bellman-Ford algorithm:

Finally vd is what we seek algorithm running time is obviously O

(VE)
-

Suppose that a weighted, directed graph G = (V, E) has a negative-weight

cycle. Give an efficient algorithm to list the vertices of one such cycle. Prove
that your algorithm is correct.
BF algorithm to find the negative right back on the road after a
point, from that point of view, along precursor reverse traversal,
you can get a negative right loop.
Because it is a negative right loop, so the relaxation process BF
algorithm, will be repeated slack negative weight loop all the
edges, that is, after the end of the relaxation process BF

algorithms, negative right loop precursor vertices must also be

negative right loop points.

b. Exercise 24.2
- Run DAG-SHORTEST-PATHS on the directed graph of Figure 24.5, using vertex r as the source.
- Suppose we change line 3 of DAG-SHORTEST-PATHS to read 3 for the first | V | - 1 vertices,
-

taken in topologically sorted order Show that the procedure would remain correct.

The PERT chart formulation given above is somewhat unnatural It would be more natural for
vertices to represent jobs and edges to represent sequencing constraints;. That is, edge (u, v)
would indicate that job u must be performed before job v Weights would then be assigned to
vertices, not edges. Modify the DAG-SHORTEST-PATHS procedure so that it finds a longest
path in a directed acyclic graph with weighted vertices in linear time.

Give an efficient algorithm to count the total number of paths in a directed

acyclic graph. Analyze your algorithm.

c. Exercise 24.3
- Run Dijkstra's algorithm on the directed graph of Figure 24.2, first using vertex s as the source

and then using vertex z as the source. In the style of Figure 24.6, show the d and values and
the vertices in set S after each iteration of the while loop.

Give a simple example of a directed graph with negative-weight edges for which Dijkstra's

Suppose we change line 4 of Dijkstra's algorithm to the following.

4 the while | the Q |> 1
This change causes the while loop to execute | V | - 1 times instead of |. V | times Is
this proposed algorithm correct?
Sepenuhnya benar , poin lainnya telah dilakukan bersantai , tidak
diupdate lagi , jika tidak merusak sifat dasar dari algoritma ini .

algorithm produces incorrect answers. Why does not the proof of Theorem 24.6 go through
when negative-weight edges are allowed?
Dijkstra prinsip algoritma adalah : setiap kali ekspansi baru dari titik
terdekat , update dari titik yang berdekatan , ketika berat semua sisi
positif , karena ada jarak tidak memperpanjang lebih titik pendek ,
sehingga jarak antara titik tidak akan pernah berubah , sehingga
memastikan kebenaran algoritma , tetapi ada batas untuk prinsip ini
adalah bahwa sisi kanan tidak boleh negatif .

We are given a directed graph G = (V, E) on which each edge (u, v) E has an associated
value r (u, v), which is a real number in the range 0 r (u, v ) 1 that represents the reliability of
a communication channel from vertex u to vertex v. We interpret r (u, v) as the probability that
the channel from u to v will not fail, and we assume that these probabilities are independent.
Give an efficient algorithm to find the most reliable path between two given vertices.

Membuat w ( u , v ) = lg ( r ( u , v ) ) , dapat diubah dengan

Algoritma Dijkstra .

Let G = (V, E) be a weighted, directed graph with weight function w: E {1, 2, ..., W} for some
positive integer W, and assume that no two vertices have the same shortest-path weights from
source vertex s. Now suppose that we define an unweighted, directed graph G '= (VU V', E ') by
replacing each edge (u, v) E with w (u, v) unit-weight edges in series. How many vertices
does G 'have? Now suppose that we run a breadth-first search on G'. Show that the order in
which vertices in V are colored black in the breadth-first search of G 'is the same as the order in
which the vertices of V are extracted from the priority queue in line 5 of DIJKSTRA when run on
G.

Figure G differs from FIG G 'is shown below:

The figure shows a graph G corresponding to each edge (u, v),

Figure G 'will add w (u, v) - 1 nodes, thus Figure G' for the number
of nodes
For traversal order to prove:
Suppose you run DIJKSTRA algorithm in Figure G, node u, v
successively removed from the priority queue. Meaning of the
questions, from the source s to the other points of the shortest
path from each other, so be sure d (u) <d (v). and because the
graph G 'breadth-first traversal on time, would be the first node u
d [u] step dyed black, then the first node v d [v] step. Therefore,
in the graph G' on the knot dyeing and order point of order when

running DIJKSTRA algorithm on the graph G removed from the

priority queue is the same.

Let G = (V, E) be a weighted, directed graph with weight function w:. E {0, 1, ..., W} for some
nonnegative integer W Modify Dijkstra's algorithm to compute the shortest paths from a given
source vertex s in O (WV + E) time.

With a two-dimensional array A [wv] achieve priority queue having a length of

node d in A [d] in the list.
EXTRACT-MIN total of O (WV) time because the whole algorithm is equivalent to
finish traverse the array again.
DECREASE-KEY total of O (E) time. Every time a check doing relax, just need to
move to the array d A corresponding position.

Modify your algorithm from Exercise 24.3-6 to run in O ((V + E) lg W) time (Hint: How many

Suppose that we are given a weighted, directed graph G = (V, E) in which edges that leave the

distinct shortest-path estimates can there be in V - S at any point in time?)

source vertex s may have negative weights, all other edge weights are nonnegative, and there
are no negative-weight cycles. Argue that Dijkstra's algorithm correctly finds shortest paths from
s in this graph.

This case will not damage the distance has been updated point.

d. Exercise 24.4
-

Find a feasible solution or determine that no feasible solution exists for the following
system of difference constraints:

x1
x1
x2
x2

-x2
-x4
-x3
-x5

1
-4
2
7
(-5, -3, 0, -1, -6, -8)

x2
x3
x4
x5

-x6
-x6
-x2
-x1

5
10
2
-1

x5 -x4 3
x6 -x3 -8

Find a feasible solution or determine that no feasible solution exists for the following
system of difference constraints:

x1 -x2 4
x1 -x5 5
x2 -x4 -6

x3 -x2 1
x4 -x1 3
x4 -x3 5

x4 -x5 10
x5 -x3 -4
x5 -x4 -8

- There is no solution, because x4 -> x2 -> x3 -> x5 -> x1 -> x4 form a negative right
loop.
Can any shortest-path weight from the new vertex v0 in a constraint graph be positive? Explain.
It is unlikely to be positive, because the maximum already zero. Not be greater
than 0.
Show how to modify the Bellman-Ford algorithm slightly so that when it is used to solve a system
of difference constraints with m inequalities on n unknowns, the running time is O (nm).
V0 vertex and his side of the n weight value 0 is actually meaningless, a start
initialization can all point v, so d [v] = 0.
Addition to that in A SUPPOSE System of Difference the Constraints, We want to by handle the
equality the Constraints of form at The XJ + XI = BK. How the Show at The the Bellman-Ford
algorithm CAN BE Adapted to the Solve the this constraint A Variety of System.

xi> = xj + bk

xi <= xj + bk

Show how a system of difference constraints can be solved by a Bellman-Ford-like algorithm

that runs on a constraint graph without the extra vertex v0.
Same exercise 24.4-5
Suppose that every row in the matrix A of a linear program Ax b corresponds to a difference
constraint, a single-variable constraint of the form xi bk, or a single-variable constraint of the
form -xi bk. Show how to adapt the Bellman-Ford algorithm to solve this variety of constraint
system.

A new office node u, so that constraints become xi - xu bk.

Initialization and d (u) = 0.

Give an efficient algorithm to solve a system Ax b of difference constraints when all of the
elements of b are real-valued and all of the unknowns xi must be integers.
First find the element with minimum absolute value in vector b , multiply it
by C to make all of the values in vector of b integer (e.g. if the minimum absolute
value is 3.102, we can multiply vector b by 1000), then solve it by bellman-ford
algorithm , and finally divide it by C
-

e. Exercise 24.5
GA KETEMU DI MANSOL PDF ADA BEBERAPA