CODEWITHSUNDEEP
algorithmclrsfloyd-warshall
oiyio
oiyio

Reputation: 5925

confusion about Floyd Warshall example on the Cormen's book

I have read and searched about Floyd Warshall algorithm and i think i understand it. But in the example which i read on the book "Introduction to the Algorithms (Thomas H. Cormen's Book)" i stacked at a point. I confused.Here is a picture which is the same in the book.My question is in the last step namely π(5). Here is the example: enter image description here http://integrator-crimea.com/images/fig653_01_0.jpg

 I think the first row of π(5) must be : 

 NIL  5   5   5   1      

 However it is written in the book :

 NIL  3   4   5   1

Could anybody clear my confusion above? Is it written wrong in the book ?

Upvotes: 0

Views: 2547

Answers (1)

Tobias
Tobias

Reputation: 1157

Let's write D_4(1,3) to mean row 1, column 3 in distance matrix D(4).

If D_5(1,2)=1 was explained by Pi_5(1,2)=3 (i.e. the shortest path from 1 to 2 goes via 3), we'd expect that D_5(1,2) = D_4(1,3) + D_4(3,2). However, D_5(1,2) = 1 but D_4(1,3) + D_4(3,2) = -1 + 4 = 3. So the Pi_5(1,2)=3 is incorrect.

Your alternative value of Pi_5(1,2)=5 is correct because 1 = D_5(1,2) = D_4(1,5) + D_4(5,2) = -4 + 5.

So you're correct that the second value in the first row of Pi(5) should be 5, not 3. I haven't checked the other values but I assume you're correct about those, too.

Upvotes: 1

Related Questions