81.动态规划求最短路径

【例5】下图表示城市之间的交通路网，线段上的数字表示费用，单向通行由A->E。试用动态规划的最优化原理求出A->E的最省费用。

如图：求v1到v10的最短路径长度及最短路径。

【样例输入】short.in

0 2 5 1 0 0 0 0 0 0
0 0 0 0 12 14 0 0 0 0
0 0 0 0 6 10 4 0 0 0
0 0 0 0 13 12 11 0 0 0
0 0 0 0 0 0 0 3 9 0
0 0 0 0 0 0 0 6 5 0
0 0 0 0 0 0 0 0 10 0
0 0 0 0 0 0 0 0 0 5
0 0 0 0 0 0 0 0 0 2
0 0 0 0 0 0 0 0 0 0

【样例输出】short.out

minlong=19

1 3 5 8 10

【算法分析】逆推法

设f[i]表示点i到v10的最短路径长度，则 f[10]=0

f[i]=min{ a[i][x]+f[x] 当a[i][x]>0 ,i时}

自己的代码：

#include
using namespace std;
#include
const int INF=0x7fffffff;
int jz[101][101],f[101],next[101];
int main()
{
int n;
scanf("%d",&n);
for(int i=1;i<=n;++i)
   for(int j=1;j<=n;++j)
   {
   scanf("%d",&jz[i][j]);
   f[i]=INF;
   }
f[n]=0;
for(int i=n-1;i>=1;--i)
   for(int j=i+1;j<=n;++j)
   {
   if(jz[i][j]!=0&&f[i]>f[j]+jz[i][j])
   {
     f[i]=f[j]+jz[i][j];
     next[i]=j;
    }
   }
printf("minlong=%d ",f[1]);
int x=1;
while(x!=n)
{
  printf("%d-->",x);
  x=next[x];
}
printf("%d",n);

return 0;
}

参考代码：

　#include

　using namespace std;

　#include

　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]=1000000; //初始化，默认每一个城市到达终点都是1000000

　 f[n]=0;

　 for (i=n-1;i>=1;i--) //从终点往前逆推，计算最短路径

　 for (x=i+1;x<=n;x++) //若f[x]=1000000表示城市x到终点城市不通

　 if ((a[i][x]>0)&&(f[x]!=1000000)&&(f[i]>a[i][x]+f[x]))

　 { //a[i][x]>0表示城市i和城市x通路

　 f[i]=a[i][x]+f[x]; //城市i到终点最短路径的值

　 c[i]=x;

　 }

　 cout<<"minlong="<<f[1]<<endl; //输出最短路径的值

　 x=1;

w　while (x!=0) //输出路过的各个城市

w　 {

w　 cout<<x<<' ';

w　 x=c[x];

w　 }

w　 cout<<endl;

w　}