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=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)/(/)\$

We have an Answer from Expert