Content deleted Content added
There is an error on the page. I'm new. I'd like someone to agree with me before I edit it |
|||
Line 24:
I have changed the path reconstruction such that the next array is updated in the main loop. This saves us the trouble of using extra procedures and illustrates a common dynamic programming pattern. [[User:Thomasda|Thomasda]] ([[User talk:Thomasda|talk]]) 20:31, 19 May 2014 (UTC)
==Is there a bug in the main loop? ==
Should the main loop for updating the 'next' matrix instead of looking like:
next[i][j] ← next[i][k]
be
next[i][j] ← next[i][k]
next[j][i] ← next[j][k]
?
I have been random fuzz testing the algorithm in Python and occasionally get a wrong path which appears fixed with the additional line.
== Floyd's and Warshall's algorithms are not the same! ==
| |||