算法 动态规划 求最短路径

动态规划：即将要求解的问题分解成多个相互重叠的子问题，根据子问题找到递推关系，即动态规划函数，然后将各子问题的解填入表中，下次就可以直接查表得到子问题的解啦。

动态规划求最短路径问题：

求解从顶点0到顶点9的最短路径，如图：

从顶点0到顶点9的最短路径可以分解为从从起点到顶点9的前一个顶点的最短距离+该顶点到9的距离。这样，从起点到每个顶点的距离都可以分解为起点到该顶点的前一个点的最短距离+前一个点到该点的距离。

用 d(i) 表示到顶点i的最短路径，c(i,j) 表示从顶点 i 到 j 的路径。

则 d(i) = d(i-1) + c(i-1,i)

注：这里 i-1 表示顶点 i 的前一个顶点，不一定有 (i-1)+1=i，例如该图中顶点9的前一个顶点有两个：7和8，取7还是8，取决于起点到7和8的距离谁更短。这样每一个顶点都可以分解为这样的子问题。

代码如下：

#include<iostream>
using namespace std;
#include<iomanip>
#define N 10 
int d[N];//最短距离
int s[N];//最短路径经过的顶点
int Rote[N][N] = {  //原路径图
 {0,4,1,0,0,0,0,0,0,0},
 {0,0,0,0,9,8,0,0,0,0},
 {0,0,0,1,6,0,8,0,0,0},
 {0,0,0,0,0,4,7,0,0,0},
 {0,0,0,0,0,0,0,5,6,0},
 {0,0,0,0,0,0,0,8,6,0},
 {0,0,0,0,0,0,0,0,5,0},
 {0,0,0,0,0,0,0,0,0,7},
 {0,0,0,0,0,0,0,0,0,3},
 {0,0,0,0,0,0,0,0,0,0}
};
int getPeak(int peak,int p[]) {
 //获取可达该顶点的个数及顶点
 int pNum = 0;//记录可达该顶点的个数
 for(int i=0;i<N;i++)
  if(Rote[i][peak]>0)
   p[pNum++] = i;//记录可达该顶点的顶点
 return pNum;
}

int getLen(int x,int y) {//获取d单路径长
 return Rote[x][y];
}

void getPrePeak(int peak) {
 //获取前一个顶点
 if(peak == 0)
  return;
 int pNum = 0;
 int p[N];//存放顶点的数组
 pNum = getPeak(peak,p);
 int x =0;
 for(int i=0;i<pNum;i++) {
  x = p[i];
  if((d[x] + getLen(x,peak)) == d[peak]) {
   s[x] = 1;
   break;
  }
 }
 getPrePeak(x);
}

void table() {
 d[0] = 0;
 for(int i=1;i<N;i++) {
  int min = 999;
  int p[N];
  int pNum = 0;
  pNum = getPeak(i,p);
  for(int j=0;j<pNum;j++) {
   int t = d[p[j]] + getLen(p[j],i);
   min = t < min ? t : min;
  }
  d[i] = min;
 }
 getPrePeak(9);
}

int main() {
 table();
 cout<<endl;
 cout<<"顶点："<<endl;
 for(int i=0;i<N;i++) {
  cout<<setw(4)<<i<<" ";
 }
 cout<<endl;
 cout<<"到该顶点的最短距离："<<endl;
 for(int i=0;i<N;i++) {
  cout<<setw(4)<<d[i]<<" ";
 }
 cout<<endl;
 cout<<"到该顶点之前经过的顶点："<<endl;
 for(int i=0;i<N;i++) {
  if(s[i] == 1)
   cout<<setw(4)<<i<<" ";
 }
 getchar();
 return 0;
}

运行结果如下：