动态规划算法

一、斐波那契数列（递推思想，动态规划算法）

二、多源最短路径（给定带权有向图（G = （V，E）），求任意两顶点（Vi，Vj）之间的最短路径）

　　弗洛伊德算法（Floyd），动态规划思想，算法复杂度大O（N的三次方）。

　　算法步骤：

　　1、先定义一个n阶的矩阵，令其对角线的值为0，若存在弧，则对应元素为弧值，否则为无穷大

　　2、逐步在原直接路径中增加中间顶点，若加入中间顶点后，路径变短，则修改之，否则维持

　　3、所有顶点试探完毕，算法结束。

  1 #include <stdio.h>
  2 #include<stack>
  3 #define N 4
  4 #define MAXINT 1000
  5 int main()
  6 {    
  7     //#ifndef N
  8     int i,j,k;
  9     /* 
 10        1.A数组, 存储顶点之间弧值,对角线值为0,
 11        顶点之间存在弧,存弧值,否则弧值MAXINT       
 12     */
 13     int A[N][N] = {   0,      5,      MAXINT,  7,
 14                       MAXINT, 0,      4,       2,
 15                       3,      3,      0,       2,
 16                       MAXINT, MAXINT, 1,       0    
 17                   };
 18                   
 19     /* 2.D数组Path数组赋值 */               
 20     int D[N][N];    //Vi到Vj的最短路径长度
 21     int Path[N][N]; //Vi到Vj的最短路径
 22 
 23     for(i=0; i<N; ++i)
 24     {
 25         for(j=0; j<N; ++j)
 26         {
 27             /* D数组赋值 */
 28             D[i][j] = A[i][j]; 
 29             /* Path数组赋值 */
 30             if(i!=j && A[i][j] < MAXINT) 
 31                 Path[i][j] = i;
 32             else 
 33                 Path[i][j] = -1;
 34         }
 35     }
 36     
 37     /* 3.计算最短路径长度及最短路径 */    
 38     //加入k顶点的最短路径长度
 39     //D[i][j] = min(D[i][j], D[i][k] + D[k][j]);
 40     for(k=0; k<N; k++)
 41     {
 42         for(i=0; i<N; i++)
 43         {
 44             for(j=0; j<N; ++j)
 45             {
 46                 if(D[i][k]+D[k][j] < D[i][j]){
 47                     D[i][j] = D[i][k] + D[k][j];
 48                     Path[i][j] = Path[k][j];
 49                 }
 50             }
 51         }
 52     } 
 53     //#endif
 54     
 55     /* 4.打印最短路径长度 */
 56     for(i=0; i<N; ++i){
 57         for(j=0; j<N; ++j)
 58             printf("%5d",D[i][j]);
 59         printf("
");
 60     }
 61     printf("
");
 62     /* 
 63         0  5  8  7
 64         6  0  3  2
 65         3  3  0  2
 66         4  4  1  0
 67     */
 68     
 69     /* 5.打印最短路径路径 */
 70     for(i=0; i<N; ++i){
 71         for(j=0; j<N; ++j)
 72             printf("%5d",Path[i][j]);
 73         printf("
");
 74     }
 75     printf("
");
 76     /* 
 77        -1  0  3  0
 78         2 -1  3  1
 79         2  2 -1  2
 80         2  2  3 -1
 81     */
 82     
 83     /* 6.打印顶点1到顶点0的最短路径 */
 84     int v1 = 1,v0 = 0;
 85     
 86     /* int arr[N] = {v0}, index = 1;
 87     while(Path[v1][v0] != -1){
 88         arr[index++] = v0 = Path[v1][v0];        
 89     }
 90         
 91     for(int i=index-1; i>=0; --i){
 92         if(i != index-1) printf(" ->");
 93         printf(" %d",arr[i]);
 94     }*/
 95     /* 1 -> 3 -> 2 -> 0 */
 96         
 97     printf("%5d",v0);
 98     while(Path[v1][v0] != -1)
 99     {
100         printf(" <- %d",Path[v1][v0]);
101         v0 = Path[v1][v0];    
102     }
103     printf("
"); 
104     /* 0 <- 2 <- 3 <- 1 */    
105     return 0;
106 }