algorithm - confusion about Floyd Warshall example on the Cormen's book -

algorithm - confusion about Floyd Warshall example on the Cormen's book -

i have read , searched floyd warshall algorithm , think understand it. in illustration read on book "introduction algorithms (thomas h. cormen's book)" stacked @ point. confused.here image same in book.my question in lastly step namely π(5). here example: http://integrator-crimea.com/images/fig653_01_0.jpg

think first row of π(5) must : nil 5 5 5 1 written in book : nil 3 4 5 1

could clear confusion above? written wrong in book ?

let's write d_4(1,3) mean row 1, column 3 in distance matrix d(4).

if d_5(1,2)=1 explained by pi_5(1,2)=3 (i.e. shortest path 1 2 goes via 3), we'd expect d_5(1,2) = d_4(1,3) + d_4(3,2). however, d_5(1,2) = 1 d_4(1,3) + d_4(3,2) = -1 + 4 = 3. pi_5(1,2)=3 incorrect.

your alternative value of pi_5(1,2)=5 is right because 1 = d_5(1,2) = d_4(1,5) + d_4(5,2) = -4 + 5.

so you're right sec value in first row of pi(5) should 5, not 3. haven't checked other values assume you're right those, too.

algorithm clrs floyd-warshall