Dynamic Programming

• divides the initial problem into several smaller instances
• and it solves the problem with descending way from bigger problems to smaller ones.

Dynamic programming is a technique that takes an opposite approach. It is similar to divide-and-conquer because it also divides an instance into smaller instances. However, to solve those instances it takes the opposite direction solving from the smallest one to the biggest and storing the results of smaller instances to reuse them later instead of recomputing them. For example, the fibonacci() function to compute the n-th number can look like

unsigned int F[25000];

unsigned int fibonacci(int n)
{
   for(int i=0;i<n;i++)
      if( i < 2 ) F[i] = 1;
      else F[i] = F[i-1] + F[i-2];
   return F[n-1];
}

unsigned int fibonacci(int n)
{
   static int i = 0;
   for(;i<n;i++)
      if( i < 2 ) F[i] = 1;
      else F[i] = F[i-1] + F[i-2];
   return F[n-1];
}

unsigned int bin(int n, int k)
{
  if( k==0 || n==k )
     return 1;
  return bin(n-1, k-1) + bin(n-1, k);
}

Floyd's algorithm for shortest path*

This graph is called directional graph because its edges have directions. In other words, we can use that way to get from vertex 1 to vertex 4, but not back. Graphs like this are also weighted because each edge has a weight associated with it. We cab think about those weight as prices or lengths of the way.

W	1	2	3	4	5
1	0	1	∞	1	5
2	9	0	3	2	∞
3	∞	∞	0	4	∞
4	∞	∞	2	0	3
5	3	∞	∞	∞	0

Those kind graphs can be represented by a square array where each element W_i,j contains the weight of the directed edge from vertex i to vertex j. The matrix W is called the adjacent matrix for the graph.

The Shortest Path problem is an optimization problem. There can be more than one candidate solution to an instance of an optimization problem.Each candidate solution has a value associated with it, and a solution to the instance is any candidate solution that has the optimal value. In the case of the Shortest Path problem, a candidate solution is a path from one vertex to another, the value is the length of the path, and the optimal value is the minimum of these lengths.

Using dynamic programming technique, we develop a cubic-time algorithm for the Shortest Path problem. Our first step would be to create a square matrix D where each element d_{i, j} contains the length of the shortest path from vertex i to vertex j. To create such a matrix, we will compute sequence of matrices D^(k) where 0≤k≤N (N is the number of vertices in the graph). Each element

d^(k)_{i, j} =  the length of a shortest path from vertex i to vertex j using only vertices with numbers less or equal k as intermediate vertices.

For example, for the graph on

The general idea of Floyd's algorithm is to compute that sequence of matrices D^(k). Obviously D⁽⁰⁾ = W and D^(N) = D - the final matrix we are interested in. Thus, all we need to do according to the dynamic programming technique is to develop a way to compute matrix D^(k) based on the previous matrix D^(k-1). We can accomplish this by considering two different cases:

1. At least one shortest path from vertex i to vertex j, using only vertices with indexes less or equal k as intermediate vertices, does not use vertex k. In this case d^(k)_{i, j} = d^(k-1)_{i, j}
2. All shortest paths from vertex i to vertex j, using only vertices with indexes less or equal k as intermediate vertices, do use vertex k. In this case d^(k)_{i, j} = d^(k-1)_{i, k} + d^(k-1)_{k, j}

void floyd(int W[][], int D[][], int N)
{
   int i, j, k;
   // initially we know only about direct connections
   for(i=0;i<N;i++)
      for(j=0;j<N;j++)
         D[i][j] = W[i][j];

   // we start updating the matrix D here
   for(k=0;k<N;k++)
      for(i=0;i<N;i++)
         for(j=0;j<N;j++)
            if( D[i][k]!= INFINITY &&
                D[k][j]!= INFINITY &&
                D[i][k]+D[k][j]<D[i][j]
               )
               D[i][j] = D[i][k]+D[k][j];
}

Exercise:

void print_shortest_path(int i, int j)
{
   if( V[i][j] != 0 ){
      print_shortest_path(i, V[i][j]);
      cout<<"->"<<V[i][j];
      print_shortest_path(V[i][j], j);
   }
}