### Present Remotely

Send the link below via email or IM

• Invited audience members will follow you as you navigate and present
• People invited to a presentation do not need a Prezi account
• This link expires 10 minutes after you close the presentation

Do you really want to delete this prezi?

Neither you, nor the coeditors you shared it with will be able to recover it again.

# Dynamic programming: Warshall's and Floyd's Algorithm

No description
by

## Guide Smile'sickOh

on 11 December 2012

Report abuse

#### Transcript of Dynamic programming: Warshall's and Floyd's Algorithm

Warshall's and Floyd's Algorithm Dynamic Programming Warshall's Algorithm Floyd’s Algorithm Computes the transitive closure of a relation All pairs shortest paths Alternatively: existence of all nontrivial paths in a digraph Transitive Closure Example of
transitive closure Wallshall's Algorithm Constructs transitive closure T as the last matrix in the sequence of n-by-n matrices R(0), … , R(k), … , R(n) where

R(k)[i,j] = 1 if there is nontrivial path from i to j with only first k vertices allowed as intermediate

Note that R(0) = A (adjacency matrix), R(n) = T (transitive closure) On the k-th iteration, the algorithm determines for every pair of vertices i, j
if a path exists from i and j with just
vertices 1,…,k allowed as intermediate 2 Warshall’s Algorithm
(recurrence) Warshall’s Algorithm
(example) Recurrence relating elements R(k) to elements of R(k-1) is: It implies the following rules for generating R(k) from R(k-1): R(k)[i,j] = R(k-1)[i,j] or (R(k-1)[i,k] and R(k-1)[k,j]) Rule 2 If an element in row i and column j is 0 in R(k-1), it has to be changed to 1 in R(k) if and only if the element in its row i and column k and the element in its column j and row k are both 1’s in R(k-1) Rule 1 If an element in row i and column j is 1 in R(k-1), it remains 1 in R(k) Warshall’s Algorithm
(matrix generation) Rule for changing zero
in warshall's algorithm Warshall’s Algorithm
(pseudocode and analysis) >Time efficiency:
>Space efficiency: Matrices can be written over their predecessors Problem: In a weighted (di)graph, find shortest paths between every pair of vertices Same idea: construct solution through series of matrices D(0), …,D(n) using increasing subsets of the vertices allowed as intermediate Floyd’s Algorithm (example) Floyd’s Algorithm
(matrix generation) Floyd’s Algorithm
(pseudocode and analysis) Example On the k-th iteration, the algorithm determines shortest paths between every pair of vertices i, j that use only vertices among 1,…,k as intermediate D(k)[i,j] = min {D(k-1)[i,j], D(k-1)[i,k] + D(k-1)[k,j]} Time efficiency: Note: Shortest paths themselves can be found, too (Problem 10) Space efficiency: Matrices can be written
over their predecessors
Full transcript