贪心算法-动态规划算法-实验报告-程序.docx

计算机算法课程实验报告

每对结点间最短路径

院系： 计算机科学与技术
班级：
姓名：
学号： U200814470

Part one
贪心法实现最短路径
一、实验目的

设计一个C程序，实现求解单源点最短路径问题。

二、实验要求

本实验要求输出最短路径值以及最短路径

三、实验内容与原理

单源点最短路径问题，即，已知一个n结点有向图G＝（V,E）和边的权函数c（e），求由某指定结点V0到其他各个结点的最短路径，这里还假定所有的权都是正的。

为了制定产生最短路径的贪心算法，对于这个问题应该想出一个多级解决办法和一种最优的量度标准。方法之一是逐条构造这些最短路径，可以使用迄今已生成的所有路径长度之和作为一种量度，为了使这一量度达到最小，其单独的每一条路径都必须具有最小长度。使用这一量度标准时，假定已经构造了i条最短路径，则下面要构造的路径应该是下一条最短的最小长度路径。首先，生成从V0到所有其它结点的最短路径。然后生成一条到第二近结点的最短路径等等。

四、程序流程图

关键思想阐述：从v0开始，只通过S中的结点并且在S外的结点w初结束的最短路径可能会减小，即DIST（w）的值可能改变。如果长度改变了，则它必定是由一条从v0开始，经过u然后到w的跟段的路径所造成的。v0到y的路径以及u到w 的路径上的中间结点应全部在S中。而且，v0到u的路径必定是这样一条最短的路径，否则就不符合DIST（w）的定义
英雌，可以得出结论，如果DIST(w)会减少，那是由于有一条从v0静u到w的更短的路，而从u到w的路径是边<u,w>.这条路径的长度是DIST(U)+C(u,w)。
分析得到程序流程图如下：

五、算法及程序说明

本算法使用贪心法设计，生成从v0到所有其它结点的最短路径的贪心方法就是按照路径长度的非降次序生成这些路径。
六、源程序

/*单源点最短路径*/

#include<stdio.h>

int search(int*,int,int,int*,int);

main(){ /*生成单源点最短路径的贪心算法*/

int COST[7][7]={{0,20,50,30,200,200,200},{200,0,25,200,200,70,200},{200,200,0,40,25,50,200},{200,200,200,0,55,200,200},{200,200,200,200,0,10,70},{200,200,200,200,200,0,50},{200,200,200,200,200,200,0}};

/*COST[i][j]表示成本邻接矩阵,200表示无穷大*/

int front_point[7]={0,0,0,0,0,0,0};/*用来存放各结点的最短路径上的前一结点*/

int DIST[7];/*DIST[i]表示第i个结点到源结点的路径长度*/

int S[7];/*S中表示对其已经生成了最短路径的那些结点，S[i]=1表示第i个结点在S中，否则不在*/

int u,num,i,w,j,k;
for(k=0;k<7;k++){ /*j对应到其他所有点的最短距离*/
for(i=0;i<7;i++){
front_point[i]=k;
}
for(i=0;i<7;i++){

S[i]=0;/*初始状态时，所有结点均不在S中*/

DIST[i]=COST[k][i];/*各结点到源结点的最短路径的初始长度为它们的直接距离*/

}

S[k]=1;/*将源结点放入S中*/

DIST[k]=0;/*自身到自身的路径为0*/

for(num=2;num<=6;num++){ /*加入五个结点到S中，最后一个不需要*/

int min=32767;

for(w=0;w<=6;w++){ /*找出不在S的结点中到源结点直接距离最短的结点*/

if(!S[w]){

if(DIST[w]<min){

min=DIST[w];

u=w; /*将所找结点位置赋值给u*/

}

}

}

S[u]=1; /*将第u结点放入S中*/

for(w=0;w<=6;w++){ /*加入u结点后，重新计算非S中结点的DIST[i]*/

if(!S[w]&&(DIST[u]+COST[u][w])<DIST[w]){

DIST[w]=DIST[u]+COST[u][w];/*若新的路径短则更新原路径*/

front_point[w]=u;

}

}

}

getch();
printf("Cost adjacency matrix\n");
for(i=0;i<=6;i++){/*输出所求结点图的邻接矩阵*/

for(j=0;j<=6;j++){

printf(" %d ",COST[i][j]);

}

printf("\n");

}

printf("value Source node to each node of the shortest path\n");

for(i=0;i<=6;i++){ /*输出结果*/

printf("v%d ",search(front_point,i,i,DIST,k)+1);
printf("v%d\n",i+1);

}

getch();

}

}

int search(int t[],int n,int m,int D[],int p){

int q=t[n];

if(q==p){

printf(" %d ",D[m]);

return(p);

}

else{

printf("v%d ",search(t,q,m,D,p)+1);

return(t[n]);

}

}
六． 实验结果
测试数据为：
{0,20,50,30,200,200,200},
{200,0,25,200,200,70,200},
{200,200,0,40,25,50,200},
{200,200,200,0,55,200,200},
{200,200,200,200,0,10,70},
{200,200,200,200,200,0,50},
{200,200,200,200,200,200,0}
注：其中200的距离代表是对应路径没有路相连。
由以上测试数据绘出数据的有向图如下所示：

实验结果如下：

注：限于篇幅，仅给出v1，v2到其余各点的最短路径及路径值。

图1－1

Part two
动态规划实现最短路径
一、实验目的与要求

设计一个C程序，实现求解每对结点之间的最短路径问题。

二、实验要求

本实验要求输出每对结点之间的最短路径值以及其最短路径

三、实验内容与原理

每对结点之间的最短路径问题是求满足下述条件的矩阵A，要求A中的任何元素A（i，j）是代表结点i到结点j的最短路径的长度。

考察G中一条由i到j的最路径，i≠j。这条路径由i出发，通过一些中间结点，在j处结束。如果k是这条最短路径上的一个中间结点，那么由i到k和由k到j的这两条子路径应分别是由i到k和由k到j的最短路径。否则，这条由i到j的路径就不是具有最小长度的路径。于是，最优性原理成立。如果k是编号最高的中间结点，那么由i到k的这条最短路径上就不会有比编号k-1更大的结点通过。同样，在k到j的那条最短路径上也不会有比编号k-1更大的结点通过。因此，可以把求取一条由i到j的最短路径看成是如下的过程：首先需要决策哪一个结点是该路径上具有最大编号的中间结点k，然后就再去求取由i到k和由k到j这两对结点之间的最短路径。当然，这两条路径上都不可能有比k-1还大的中间结点。

四、程序流程图

五、源程序

/*每对结点之间的最短路径*/

#include<stdio.h>

void main(void){ /*求每对结点之间的最短路径*/

int cost[3][3]={{0,4,11},{6,0,2},{3,100,0}};/*输入所求结点图的邻接矩阵,100表示无穷大*/

int a[3][3]; /*结点之间的最短路径矩阵*/

int path[3][3][3]={0};/*存放结点对之间的路径，初值均为*/

int i,j,k;

for(i=0;i<=2;i++){

for(j=0;j<=2;j++){

a[i][j]=cost[i][j];/*将cost[i][j]复制到a[i][j]*/

}

}

for(k=0;k<=2;k++){ /*对最高下标为k的结点的路径*/

for(i=0;i<=2;i++){ /*对于所有可能的结点对*/

for(j=0;j<=2;j++){

if(a[i][j]>(a[i][k]+a[k][j])){

a[i][j]=a[i][k]+a[k][j];

path[i][j][k]=k;/*将k结点加入到结点对（i，j）的最短路径中*/

}

}

}

}

printf("Cost adjacency matrix\n");

for(i=0;i<=3;i++){/*输出所求结点图的邻接矩阵*/

if(i){

printf("v%d ",i);/*打印矩阵的行标v1,v2,……，vn*/

}

for(j=0;j<=2;j++){

if(!i){

printf(" v%d",j+1);/*打印矩阵的列标*/

}

else{

printf("%d ",cost[i-1][j]);

}

}

printf("\n");

}

printf("Node of Source node to each node of the shortest path value\n");

for(i=0;i<=2;i++){/*输出经算法产生的结点间的最短路径矩阵*/

for(j=0;j<=2;j++){

printf("v%dv%d ",i+1,j+1);/*打印结点对*/

printf("v%d ",i+1);/*打印每对结点之间的最短路径*/

for(k=0;k<=2;k++){

if(path[i][j][k]){/*打印出已存入的路径*/

printf("v%d ",path[i][j][k]+1);

}

else{ /*对齐输出格式*/

printf(" ");

}

}

printf("v%d ",j+1);

printf(" %d \n\n",a[i][j]);/*打印最短路径值*/

}

}

getch();

}
六、实验结果
测试数据：
{0,4,11},
{6,0,2},
{3,100,0}
注：其中100表示没有该条路径，用一个相对很大的数代替无穷大。
由以上测试数据得到如下测试数据图：

2
4
1

6
11 3
3
2

实验结果截图如下所示：

七、实验感想及心得体会

1． 在做这个实验时，我一直在思考一个问题，这两个算法究竟有什么区别，因为我觉得第二个算法从设计思想以及到语言描述都比第一个算法第简单，但一个算法并未降低此问题的是时间复杂度，所以我觉得对于求单源路径使用动态规划的设计思想可使程序更简单。经过仔细分析才领悟到，单源路径的贪心算法过人之处在于：它能以较快的速度计算出v0到所有结点中最n短的路径长度。而动态规划则必须循环完所有的结点后才能得出某一对结点的最短路径长度

2． 由于课本上已经给出了实现此算法的形式化描述，所以此次课设相对以前的c以及数据结构来说，是比较简单的，但有一点，输出路径需要自己设计，关于这一点我考虑了两种方法：

其中对于单源路径我使用的方法是：定义一个一维数组，长度为图的结点个数，

初始值为零，用来存放每个结点最短路径上的前一结点，最后根据这个数组的信息可以输出路径，为了使输出从起点到终点，还使用了递归。

对于第二个实验，我定义了一个三位数组，长度为n*n*n,存放每一对结点的完整路径，初始值为零，最后根据这个数组的信息直接输出。

3．总之，经过本次实验，收获很大，通过编程，以及上机调试，使我对两种算法的基本思想以及两个具体的问题理解得更加透彻，再也不是那种模模糊糊的感觉了.