动态规划之最短路径问题-白红宇

动态规划之最短路径问题

阅读量：7081 次

发布时间：2019-06-28

本文共 3016 字，大约阅读时间需要 10 分钟。

问题参考：

现有一张地图，各结点代表城市，两结点间连线代表道路，线上数字表示城市间的距离。如图1所示，试找出从结点A到结点E的最短距离。

我们可以用深度优先搜索法来解决此问题，该问题的递归式为

其中是与v相邻的节点的集合，w(v,u)表示从v到u的边的长度。

这个程序的效率如何呢？我们可以看到，每次除了已经访问过的城市外，其他城市都要访问，所以时间复杂度为O(n!)，这是一个“指数级”的算法。

首先，我们来观察一下这个算法。在求从B1到E的最短距离的时候，先求出从C2到E的最短距离；而在求从B2到E的最短距离的时候，又求了一遍从C2到E的最短距离。也就是说，从C2到E的最短距离我们求了两遍。同样可以发现，在求从C1、C2到E的最短距离的过程中，从D1到E的最短距离也被求了两遍。而在整个程序中，从D1到E的最短距离被求了四遍。如果在求解的过程中，同时将求得的最短距离"记录在案"，随时调用，就可以避免这种情况。于是，可以改进该算法，将每次求出的从v到E的最短距离记录下来，在算法中递归地求MinDistance(v)时先检查以前是否已经求过了MinDistance(v)，如果求过了则不用重新求一遍，只要查找以前的记录就可以了。这样，由于所有的点有n个，因此不同的状态数目有n个，该算法的数量级为O(n)。

更进一步，可以将这种递归改为递推，这样可以减少递归调用的开销。

代码如下：

[cpp]

#include <iostream>

#include <fstream>

usingnamespace std;

ifstream fin("in.txt");

#define maxLength 20

int matrix[maxLength][maxLength]; //有向图的邻接表

int minPath[maxLength]; //存储这每个节点到终点的最短路径

int trace[maxLength]; //记录下最短线路

int v_n; //节点个数

int MinDistance(int v)

{

if(minPath[v]>0) return minPath[v];

if(v==v_n-1) return 0; //边界值

int min=1000,t,j;

for(int i=v+1;i<v_n;i++)

{

if(matrix[v][i]>0)

{

t = matrix[v][i]+MinDistance(i);

if(min>t){ min=t; j=i;}

}

}

minPath[v]=min;

trace[v]=j;

return minPath[v];

}

int main()

{

fin>>v_n;

for(int i=0;i<v_n;i++)

{

for(int j=0;j<v_n;j++)

{

fin>>matrix[i][j];

cout<<matrix[i][j]<<"-";

}

cout<<endl;

}

memset(minPath,0,sizeof(int)*maxLength);

memset(trace,0,sizeof(int)*maxLength);

int minD = MinDistance(0);

cout<<"最短路径："<<minD<<endl;

i=0;

cout<<"1-->";

while(minD>0)

{

cout<<trace[i]+1<<"-->";

minD = minD-matrix[i][trace[i]];

i = trace[i];

}

cout<<endl;

return 0;

}

#include 
      
       #include 
       
        using namespace std;ifstream fin("in.txt");#define maxLength 20int matrix[maxLength][maxLength];   //有向图的邻接表int minPath[maxLength];             //存储这每个节点到终点的最短路径int trace[maxLength];               //记录下最短线路int v_n; //节点个数int MinDistance(int v){	if(minPath[v]>0) return minPath[v]; 	if(v==v_n-1) return 0;     //边界值	int min=1000,t,j;	for(int i=v+1;i
        
         0) 		{				t = matrix[v][i]+MinDistance(i);			if(min>t){ min=t; j=i;}		}	}	minPath[v]=min;	trace[v]=j;	return minPath[v];}int main(){		fin>>v_n;	for(int i=0;i
         
          >matrix[i][j];			cout<
          
           <<"-";		}		cout<
           
            "; while(minD>0) { cout<
            
             <<"-->"; minD = minD-matrix[i][trace[i]]; i = trace[i]; } cout<