- 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 61 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
-
answerhappygod
- Site Admin
- Posts: 899604
- Joined: Mon Aug 02, 2021 8:13 am
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
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
Join a community of subject matter experts. Register for FREE to view solutions, replies, and use search function. Request answer by replying!