CSE408
Dynamic Programming
Floyd and warshal
binomial coff
Dynamic Programming
• It divide the problem into series of overlapping
subproblems.
• Two features
1. Optimal substructure
2. Overlapping problem
Dynamic programming is a problem-solving method that
breaks down complex problems into smaller, overlapping
subproblems, solves them once, and stores the solutions to
avoid redundant calculations, ultimately finding the optimal
solution to the original problem.
• Memoization/Tabulation: To avoid redundant
calculations, dynamic programming uses
techniques like memoization (top-down
approach) or tabulation (bottom-up approach)
to store and reuse the solutions to
subproblems.
Binomial Coefficient
Time complexity - O(n*k)
Using naïve recursion – O(2^n)
All-Pairs Shortest Path Problem
Suppose we are given a directed graph G=(V,E)
and a weight function w: E->R.
We assume that G does not contain cycles of
weight 0 or less.
The All-Pairs Shortest Path Problem asks to find
the length of the shortest path between any pair
of vertices in G.
8
Quick Solutions
If the weight function is non-negative for all
edges, then we can use Dijkstra’s single source
shortest path algorithm for all vertices to solve
the problem.
O(E log V) -> V times
This gives an O(V3log V) time complexity for
algorithm on graphs with V vertices.
9
Quick Solution
For arbitrary weight functions, we can use the
Bellman-Ford algorithm applied to all vertices.
This gives an O(V4) time complexity for
algorithm on graphs with V vertices.
O(V.E) -> V times
10
Floyd-Warshall
We will now investigate a dynamic programming
solution that solved the problem in O(V3) time
for a graph with V vertices.
This algorithm is known as the Floyd-Warshall
algorithm, but it was apparently described
earlier by Roy.
11
Floyd-Warshall
• The Floyd Warshall Algorithm is an all-pair shortest path
algorithm that uses Dynamic Programming to find the
shortest distances between every pair of vertices in a graph.
• This algorithm works for both the directed and undirected
weighted graphs and can handle graphs with both positive
and negative weight edges.
Representation of the Input
We assume that the input is represented by a
weight matrix W= (wij)i,j in E that is defined by
wij= 0 if i=j
wij= w(i,j) if ij and (i,j) in E
wij= if ij and (i,j) not in E
22
Format of the Output
If the graph has n vertices, we return a distance
matrix (dij), where dij the length of the path from
i to j.
23
Intermediate Vertices
Without loss of generality, we will assume that
V={1,2,…,n}, i.e., that the vertices of the graph
are numbered from 1 to n.
Given a path p=(v1, v2,…, vm) in the graph, we
will call the vertices vk with index k in {2,…,m-1}
the intermediate vertices of p.
24
Key Definition
The key to the Floyd-Warshall algorithm is the
following definition:
Let dij(k) denote the length of the shortest path
from i to j such that all intermediate vertices are
contained in the set {1,…,k}.
25
Remark
Consider a shortest path p from i to j such that
the intermediate vertices are from the set
{1,…,k}.
• If the vertex k is not an intermediate vertex on
p, then dij(k) = dij(k-1)
If the vertex k is an intermediate vertex on p,
then dij(k) = dik(k-1) + dkj(k-1)
26
Remark
Therefore, we can conclude that
dij(k) = min{dij(k-1) , dik(k-1) + dkj(k-1)}
27
Recursive Formulation
If we do not use intermediate nodes, i.e., when
k=0, then
dij(0) = wij
If k>0, then
dij(k) = min{dij(k-1) , dik(k-1) + dkj(k-1)}
28
The Floyd-Warshall Algorithm
Floyd-Warshall(W)
n = # of rows of W;
D(0) = W;
for k = 1 to n do
for i = 1 to n do
for j = 1 to n do
dij(k) = min{dij(k-1) , dik(k-1) + dkj(k-1)};
return D(n);
29
Time and Space Requirements
The running time is obviously O(n3), where n is
total number of vertices.
However, in this version, the space requirements
are high. One can reduce the space from O(n3)
to O(n2) by using a single array d.
30
