算法实验报告第二次华科..doc

课 程 实 验 报 告 课程名称： 计算机算法基础 专业班级：计算机科学与技术1209班 学 号： 指导老师： 何 琨 报告日期： 2012-12-28 计算机科学与技术学院 目录 一．实验一 3 1．实验题目 3 2．设计思路 3 3．程序源代码 3 4．运行演示 6 二．实验二 8 1．实验题目 8 2．设计思路 8 3．程序源代码 8 4．运行演示 12 一．实验一 1．实验题目 单源最短路径问题： 已知一个n结点有向图G=(V,E)和边的权函数c(e)，求由G中某指定结点v0到其它各结点的最短路径。假定边的权值为正。 2．设计思路 应用贪心算法求解。 1) 度量标准 生成的所有路径长度之和作为标准。为这一量度达到最小，其单独的每一条路径都具有最小长度。 按照路径长度的非降次序生成这些路径。，生成一条到最近结点的短路径然后，生成一条到第二近结点的最短路径，等等。 #include stdio.h #include stdlib.h #define N 1000 void shortestPaths(int v,int *COST,int *DIST,int n);//最短路径生成函数 int min(int x,int y); void outArray2(int *arr,int row,int col);//输出成本的邻接矩阵 void outArray1(int *arr,int n);//输出更新后其它结点到起始结点的路径长度 int main() { int COST[7][7]={ {0,20,50,30, N, N, N}, {N, 0,25, N, N,70, N}, {N, N, 0,40,25,50, N}, {N, N, N, 0,55, N, N}, {N, N, N, N, 0,10,70}, {N, N, N, N, N, 0,50}, {N, N, N, N, N, N, 0} }; int DIST[7]; int v=0; printf(成本邻接矩阵：\n); outArray2(COST[0][0],7,7); //生成0号结点到1至6号结点的最短路径 shortestPaths(v,COST[0][0],DIST,7); return 0; } void shortestPaths(int v,int *COST,int *DIST,int n) {//G是一个n结点有向图，它由其成本邻接矩阵COST[n][n]表示，DIST[j]被置以结点v到 //结点j的最短路径长度，这里1=j=n;DIST[v]被置成0 int S[n]; int pre[n];//p[w]记录起始结点到结点w的最短路径中的w前一结点 int u,num,i,w; int tv,td=0; //初始化：结点v以外的结点未被选中，并更新路径长度为v到其它结点的初始成本 for(i=0;in;i++) { S[i]=0; *(DIST+i)=*(COST+v*n+i); pre[i]=0; } S[v]=1; DIST[v]=0; //更新路径长度 for(num=1;numn;num++) { //选择距离结点 v 最近的结点 w for(w=1;wn;w++) { if(S[w]==0) { td=DIST[w]; tv=w; break;