Lecture 24.
Today we looked at the FWI algorithm also
known as the Floyd-Warshall algorithm. This simple to code algorithm uses an
adjacency matrix to determine the weights of shortest paths between all pairs of
vertices in a weighted directed graph. This algorithm uses a technique called
"dynamic programming". Along the way I defined the "principle of optimality
condition" used to justify the correctness of the algorithm.
Posted: Fri - March 9, 2007 at 10:07 AM