先简单叙述一下动态规划的步骤
问题和思路
代码如下
1 #include<bits/stdc++.h>
2 using namespace std;
3 int cost[10];
4 int path[10];
5 int array1[10][10];
6 int main()
7 {
8 memset(cost,0,sizeof(cost));
9 memset(path,0,sizeof(path));
10 memset(array1,0,sizeof(array1));
11 cout << "请输入多段图的边数" << endl;
12 int m;//18
13 cin >> m;
14 cout << "请依次输入多段图的起点终点和路径长度" << endl;
15 int start;
16 int stop;
17 int length;
18 for(int i=0;i<18;i++){
19 cin >> start >> stop >> length;
20 array1[start][stop]=length;
21 }
22 for(int i=8;i>=0;i--){
23 cost[i]=9999;
24 for(int j=i;j<10;j++){
25 if(array1[i][j]!=0){//等于零表示之间没有路
26 if(array1[i][j]+cost[j]<cost[i]){//此时找到一条更短的路
27 path[i]=j;//更新path[i]
28 cost[i]= array1[i][j]+cost[j];//更新从该节点出发的最短路径
29 }
30 }
31 }
32 }
33 cout << "最短路径长度是" << cost[0];
34 cout <<endl;
35 cout << "最短路径为"<< endl;
36 int i=0;
37 cout << "0--->";
38 while(true){
39 cout << path[i];
40 i=path[i];
41 if(i==9){
42 break;
43 }
44 cout << "--->" ;
45 }
46 return 0;
47 }
运行结果如下
