多短图的最短路径问题-动态划分法

应用示例：
在车辆中安装了车辆导航系统，人们就可以不必为迷路、绕远而担心，只需点击所
在位置与目的地，路径规划会帮你找出到达目的地的最短路线。
路径规划是基于具有拓扑结构的道路网络，在车辆行驶前或行驶过程中寻找车辆
从起始点到达目的地的最佳行车路线的过程，它是多段图最短路径问题的典型应用。
对以下多段图，求出从原点1到终点10的最短路径。

分析：

第二行是cost数组，第三行是path数组

输入：
输入：
10 16
0 1 3
0 2 8
0 3 5
1 4 13
1 5 3
2 4 6
2 6 5
3 5 7
3 6 4
4 7 4
4 8 2
5 7 3
5 8 3
6 8 8
7 9 7
8 9 9

源代码：

#include <iostream>
using namespace std;
const int N = 20;
const int MAX = 1000;
int arc[N][N]; //存储弧上的权值

int CreatGraph(){
	int i,j,k;
	int weight;
	int vnum,arcnum;
    cout<<"请输入顶点个数和边的个数：";
	cin>>vnum>>arcnum;
	for(i=0;i<vnum;i++)
		for(j=0;j<vnum;j++)
			arc[i][j]=MAX;
	for(k=0;k<arcnum;k++){
		cout<<"请输入边的两个顶点和权值:";
		cin>>i>>j>>weight;
        arc[i][j]=weight;
	}
    return vnum;
}

int BackPath(int n){
	int i,j;
	int cost[N];int path[N];
	for(i=1;i<n;i++)
	{
		cost[i]=MAX;
		path[i]=-1;
	}
	cost[0]=0;path[0]=-1;
	for(j=1;j<n;j++){
		for(i=j-1;i>=0;i--)
		{
			if(arc[i][j]+cost[i]<cost[j])
			{
				cost[j]=arc[i][j]+cost[i];
				path[j]=i;
			}
		}
	}
	cout<<"路径是倒序:";
	cout<<n;
	i=n-1;
	while(path[i]>=0){
		cout<<"<-"<<path[i]+1;
		i=path[i];
	}
	return cost[n-1];
}

int main()
{     int n = CreatGraph( );
      int pathLen = BackPath(n);
      cout<<endl<<"最短路径的长度是:"<<pathLen<<endl;
      return 0;
}

运行结果：

时间复杂度：理论时间复杂度：O（m+k）–(m为边数个数，k为划分段数),
实际时间复杂度O(n^2)