Algorithms in a Nutshell

(^166) | Chapter 6: Graph Algorithms
For values ofk>0, we assume when computingdistkthat we have already
computeddistk–1(in dynamic programming, one must solve the subproblems in
an appropriate order).
FLOYD-WARSHALLproceeds by incrementingkfrom 0 tonuntildistn[][] is
computed. When computingdistk[i][j], we need to know whether a shortest path
fromvitovj(which may only pass through verticesv 1 ,v 2 ,...,vkin addition tovi
andvj) passes through vertexvk:
Figure 6-18. Floyd-Warshall fact sheet
Algorithms in a Nutshell
Algorithms in a Nutshell By Gary Pollice, George T. Heineman, Stanley Selkow ISBN:
9780596516246 Publisher: O'Reilly Media, Inc.
Prepared for Ming Yi, Safari ID: [email protected]
Licensed by Ming Yi
Print Publication Date: 2008/10/21 User number: 594243
© 2009 Safari Books Online, LLC. This PDF is made available for personal use only during the relevant subscription term, subject to the Safari Terms of Service. Any other use