动态规划法实现有向图的最短路径实验
实验题目：
设计一个求解有向图，单源最短路径的算法
实验目的：
1）了解，并掌握分支限界算法思想
2）会编写常见算法。

实验要求：
1.编写实验代码
2.分析算法时间和空间复杂度
实验主要步骤：
1 算法代码
package suanfa;
publicclass ShortPath{
privatestatic Integer M = Integer.MAX_VALUE;
publicstaticvoid main(String[]args){
int[][]c={{M,4,2,3,M,M,M,M,M,M},
{M,M,M,M,9,8,M,M,M,M},
{M,M,M,M,6,7,8,M,M,M},
{M,M,M,M,M,4,7,M,M,M},
{M,M,M,M,M,M,M,5,6,M},
{M,M,M,M,M,M,M,8,6,M},
{M,M,M,M,M,M,M,6,5,M},
{M,M,M,M,M,M,M,M,M,7},
{M,M,M,M,M,M,M,M,M,3},
{M,M,M,M,M,M,M,M,M,M}};
shortPath(10,c);
}
publicstaticvoid shortPath(int n,int[][]c){
int[] cost=newint[n];//cost[i]存储i到n-1的子问题的最短路径值
int[] path=newint[n];//path[i]存储状态，使cij+cost[i]最小的j值
//对数组cost[n]和path[n]进行初始化
for(int i=0;i<n-1;i++){
cost[i]=M;
path[i]=-1;
}
cost[9]=0;
for(int i=n-2;i>=0;i--){
for(int j=n-1;j>=i;j--){
//得到i的邻接点
if(c[i][j]<M&&cost[i]>(c[i][j]+cost[j])){
cost[i]=c[i][j]+cost[j];
path[i]=j;
}
}
}
System.out.println("最短路径长度为："+cost[0]);
System.out.print("最短路径为：");
int i=0;
System.out.print("0");
while(i!=n-1){
System.out.print("-->"+path[i]);
i=path[i];
}
}
}
2 程序运行结果
4 算法复杂度分析
设节点个数为n个
算法的循环的次数为n*n次，算法的时间复杂度为O(n^2)
算法需要保存一个矩阵，故算法的空间复杂度为O(n^2)。