Page 1 of 1
In the class exercise we saw that we can save time by exiting Bellman-Ford early when there are no updates on a pass of
Posted: Sun May 15, 2022 8:51 am
by answerhappygod
- In The Class Exercise We Saw That We Can Save Time By Exiting Bellman Ford Early When There Are No Updates On A Pass Of 1 (98.11 KiB) Viewed 63 times
In the class exercise we saw that we can save time by exiting Bellman-Ford early when there are no updates on a pass of the outer loop. Can we similarly exit the outer loop (line 3) of Floyd-Warshall early when line 6 does not make any updates in the most recent pass? FLOYD-WARSHALL'(W) 1 n = W.rows 2 D = W 3 for k = 1 ton 4 for i = 1 ton 5 for j = 1 ton 6 dij = min (dij, dik +dkj) 7 return D True False