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=1
text( to )
n|$
| |$text( ) text(for )
i=1
text( to )
n|$
| |$text( ) text( ) text(for )
j=1
text( to )
n|$
|
|$
| text( ) text( ) text( ) d_{ij} =
min{d_(ij),d_(-){ik}+d_(-){kj}}|$
|
|$
| text(return )
(D)/(/)$