动态规划 最短路径

动态规划求有向无环图的最短路径

 

问题描述如下：

---

 

 

---

具体代码实现：

 1 #include<stdlib.h>
 2 #include<stdio.h>
 3 #define x 9999
 4 #define max 9999
 5 int data[10][10];
 6 int dist[10];//记录最短路径为多少
 7 int path[10];//记录最短路径
 8 int kmin(int,int);
 9 void fpath(int a[][10]);
10 int froute(int a[][10]);
11 void main()
12 {
13     int i,m;
14     int a[10][10]={
15     {x,4,2,3,x,x,x,x,x,x},
16     {x,x,x,x,10,9,x,x,x,x},
17     {x,x,x,x,6,7,10,x,x,x},
18     {x,x,x,x,x,3,8,x,x,x},
19     {x,x,x,x,x,x,x,4,8,x},
20     {x,x,x,x,x,x,x,9,6,x},
21     {x,x,x,x,x,x,x,5,4,x},
22     {x,x,x,x,x,x,x,x,x,8},
23     {x,x,x,x,x,x,x,x,x,4},
24     {x,x,x,x,x,x,x,x,x,x}};
25 
26     /*for (i=0;i<10;i++)
27     {
28         for(j=0;j<10;j++)
29         printf("%d  ",a[i][j]);
30         printf("\n");
31     }*/
32     fpath(a);
33         printf("最短路径大小为:  %d\n",dist[9]);
34 
35     m=froute(a);
36     for(i=m-1;i>=0;i--)
37         printf("最短路径经过:   %d\n",path[i]);
38 }
39 void fpath(int a[][10])
40 {
41     int i,j,k;
42     dist[0]=0;
43     for(i=1;i<10;i++)
44     {
45         k=max;
46         for(j=0;j<i;j++)
47         {
48             if(a[j][i]!=x)
49                 if((dist[j]+a[j][i])<k)
50                     k=dist[j]+a[j][i];    
51         }
52         dist[i]=k;
53     }
54 }
55 int froute(int a[][10])
56 {
57     int j,b,k=1,i=9;
58     path[0]=10;
59     while(i>0)
60     {
61         for(j=i-1;j>=0;j--)
62         {
63             if(a[j][i]!=x)
64             {
65                 b=dist[i]-a[j][i];
66                 if(b==dist[j])
67                 {
68                     path[k++]=j+1;
69                     i=j;
70                     break;
71                 }
72             }
73 
74         }
75     }
76         return k;
77 }
78 
79 
80