Home /
Expert Answers /
Computer Science /
problem-3-modify-the-bellman-ford-algorithm-so-that-it-sets-v-d-to-infty-for-all-vertices-pa157
(Solved): Problem 3 Modify the Bellman-Ford algorithm so that it sets |$v.d|$ to |$-\infty |$ for all vertices ...
Problem 3 Modify the Bellman-Ford algorithm so that it sets
|$v.d|$to
|$-\infty |$for all vertices
|$v|$for which there is a negative-weight cycle on some path from the source to
|$v|$. Problem 4 Show how to use the output of the FloydWarshall algorithm to detect the presence of a negative-weight cycle. Problem 5 As it appears on page 657 of the text, the Floyd-Warshall algorithm requires
|$| Theta
(n^(3))|$| space, since it creates
|$(d)_(ij)^(^()){(k)}|$for
|$i,j,k|
=1,2,dots,n|$|. Show that the procedure
$$text(FLOYDWARSHALL')|$, which simply drops all the superscripts, is correct, and thus only
|$\Theta (n^(2))|$space is required. |$text(FLOYD-WARSHALL')(W, n)|$
|$D|
=(W)/(/)$
|$| text(for )
k=1text( to )
n|$| |$text( ) text(for )
i=1text( to )
n|$| |$text( ) text( ) text(for )
j=1text( to )
n|$|
|$| text( ) text( ) text( ) d_{ij} =
min{d_(ij),d_(-){ik}+d_(-){kj}}|$|
|$| text(return )
(D)/(/)$