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

问题描述如下：

---

 

 

---

 

具体代码实现：

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 《新程序员》：云原生和全面数字化实践50位技术专家共同创作，文字、视频、音频交互阅读

总结

以上是生活随笔为你收集整理的动态规划 最短路径的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。