动态规划求解网络最优路径

1-j]=d[N-1-i+j][N-1-j]+shu[N-2-i][N-1];u_x[N-2-i+j][N-1-j]=N-1-i+j;u_y[N-2-i+j][N-1-j]=N-1-j;}elseif(j==i+1){d[N-2-i+j][N-1-j]=d[N-2-i+j][N-j]+hen[N-1][N-2-i];u_x[N-2-i+j][N-1-j]=N-2-i+j;u_y[N-2-i+j][N-1-j]=N-j;}else{k1=d[N-2-i+j][N-j]+hen[N-2-i+j][N-1-j];k2=d[N-1-i+j][N-1-j]+shu[N-2-i+j][N-1-j];if(k1<=k2){d[N-2-i+j][N-1-j]=k1;u_x[N-2-i+j][N-1-j]=N-2-i+j;u_y[N-2-i+j][N-1-j]=N-j;}else{d[N-2-i+j][N-1-j]=k2;u_x[N-2-i+j][N-1-j]=N-1-i+j;u_y[N-2-i+j][N-1-j]=N-1-j;}}}for(i=N-2;i>=0;i--)for(j=0;j<=i;j++){k1=d[i-j][j+1]+hen[i-j][j];k2=d[i-j+1][j]+shu[i-j][j];if(k1<=k2){d[i-j][j]=k1;u_x[i-j][j]=i-j;u_y[i-j][j]=j+1;}else{d[i-j][j]=k2;u_x[i-j][j]=i-j+1;u_y[i-j][j]=j;}}printf("最短路径为:\n ");for(i=1;i<=2*N-5;i++){printf("(%d,%d)\n",x,y);x=u_x[x][y];y=u_y[x][y];}printf("最短路径长度为:%d\n",d[0][0]);return0;}继续阅读