动态规划城市最短路径问题_动态规划 受限最短路径长度问题

问题描述
最短路径问题(Shortest path problem)：再不回退的前提下，找到A到F的最短路径

算法分析：

//倒推法
#include<bits/stdc++.h>
using namespace std;
int main()
{
	long n,i,j,x,f[100],c[100],a[100][100];
	memset(a,0,sizeof(a));
	memset(c,0,sizeof(c));
	cin>>n; 
	for(i=1;i<=n;i++)
		for(j=1;j<=n;j++)
			cin>>a[i][j];
	
	for(i=1;i<=n;i++) 
	f[i]=2100000000;//初始化，默认为每一个城市到达终点的距离
	f[n]=0;
	for(i=n-1;i>=1;i--)
	for(x=i+1;x<=n;x++)
	if(a[i][x]>0&&(f[x]!=2100000000&&f[i]>a[i][x]+f[x]))
	{
		f[i]=a[i][x]+f[x];
		c[i]=x;
	 } 
	 cout<<f[1]<<endl;
	 x=1;
	 while(x!=0)
	 {
	 	cout<<x<<" ";
	 	x=c[x];
	 }
	 cout<<endl;
}
/*
0 5 3 0 0 0 0 0 0 0 0
5 0 0 1 5 3 0 0 0 0 0 
3 0 0 0 8 0 4 0 0 0 0
0 1 0 0 0 0 0 5 6 0 0
0 6 8 0 0 0 0 5 6 0 0 
0 3 0 0 0 0 0 0 0 8 0
0 0 4 0 0 0 0 0 0 3 0
0 0 0 5 5 0 0 0 0 0 3
0 0 0 6 0 0 0 0 0 0 4
0 0 0 0 0 8 3 0 0 0 3
0 0 0 0 0 0 0 3 4 3 0
*/

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46