算法设计程序设计报告.doc

发布时间：2022-05-29 发布人：admin 分类：说明书资料大小：0.11M 资料格式：doc 举报版权申诉

xzsfxhy-3069028-4744302542918562503.doc.pdf-第1页.png

第1页 / 共7页

xzsfxhy-3069028-4744302542918562503.doc.pdf-第2页.png

第2页 / 共7页

xzsfxhy-3069028-4744302542918562503.doc.pdf-第3页.png

第3页 / 共7页

xzsfxhy-3069028-4744302542918562503.doc.pdf-第4页.png

第4页 / 共7页

xzsfxhy-3069028-4744302542918562503.doc.pdf-第5页.png

第5页 / 共7页

xzsfxhy-3069028-4744302542918562503.doc.pdf-第6页.png

第6页 / 共7页

xzsfxhy-3069028-4744302542918562503.doc.pdf-第7页.png

第7页 / 共7页

文本预览

算法设计程序设计报告报告题目：实现校园里从一个地点到另一个地点的最短路径课设题目：算法分析和设计一．实验目的用贪心算法实现实现校园里从一个地点到另一个地点的最短路径二．实验题目和原理分析在校园里有不少于 10 个的地方，有的两点之间有路，有的两点之间并没有路，从中选出起点、终点，找从起点到终点的最佳路径，并输出。程序采用了 Dijkstras 算法。三．具体的程序设计思想

要求：设计从一个地点到另一个地点的最短路径，用 C++实现，给出程序的正确运行结果。设置顶点集合 S 并不断地做贪心选择来扩充这个集合。一个顶点属于集合 S 当且仅当从源到该顶点的最短路径长度已知。初始时，S 中仅含有源。设 u 是 G 的某一个顶点，把从源到 u 且中间只经过 S 中顶点的路径为从源到 u 的特殊路径，并用数组 dist 记录当前每个顶点所对应的最短特殊路径长度。Dijkstras 算法每次从 V-S 中取出具有最短特殊路长度的顶点 u，将 u 添加到 S 中，同时对数组 dist 进行必要的修改。一旦 S 包含了所有 V 中顶点，dist 就记录了从源到所有其他顶点之间的最短路径长度。四．具体代码及实现 #include #include using namespace std; const float Max_Num = 12000; const int Num = 10; bool Dijkstra(int v, float (*a)[Num],float *dist, int *prev) { int h = Num; if(v < 0 || v > Num) return 0; bool s[Num]; //初始化 for(int i = 0; i < h; i++) { if(i != v) { dist[i] = a[v][i]; s[i] = false; if(dist[i] == Max_Num) prev[i] = -1; else prev[i] = v; } else { dist[v] = 0; s[v] = true; prev[v] = -1; } } //dist[v] = 0; //s[v] = true;

for(int j = 0; j < h-1; j++) { float temp = Max_Num; int u = v; for(int k = 0; k < h; k++) //找 u 到剩下点的最短路径件 { if((!s[k]) && (dist[k] < temp)) //s[k] == false 时满足条 { } u = k; temp = dist[k]; } s[u] = true; for(int m = 0; m < h; m++) if((!s[m]) && (a[u][m] < Max_Num)) { float newdist = dist[u]+a[u][m]; if(newdist < dist[m]) { dist[m] = newdist; prev[m] = u; } } } } int main() { string _str[Num]; float c[Num][Num]; float min = 0; float dist[Num]; int prev[Num]; int way, qu; int nn, nn1; int i, j; int sum = 9; _str[0] = "三区四栋"; _str[1] = "四食堂"; _str[2] = "六食堂"; _str[3] = "图书馆"; _str[4] = "一号楼";

_str[5] = "二号楼"; _str[6] = "主 A 楼"; _str[7] = "西门"; _str[8] = "计算机学院"; _str[9] = "前门"; for(i = 0; i>nn; while(nn!=0 && nn!=1) { cout<<"输入错误请重输："; cin>>nn; } while(nn!=0) { sum++; cout<<"输入节点：（i j）"; int a, b; float aa; cin>>a>>b; cout<<"权值:"; cin>>aa; c[a][b] = aa; c[b][a] = aa; //cout<>nn; while(nn!=0 && nn!=1) { cout<<"输入错误请重输：";

cin>>nn; } } if(sum < (Num-1)) { cout<<" 输入错误，重新开始."; exit(1); } cout<<"输入你所在的位置及所要到的地方："; cin>>way>>qu; Dijkstra(way, c, dist, prev); nn1 = qu; min = dist[nn1]; cout<<"==================================================\n"; cout<<"你要查询从"<<_str[way]<<"到"<<_str[qu]<<"\n"; if(nn1!=way) { cout<<_str[nn1]; while(nn1!=way) { //prev[way] == -1 cout<<"<-"<<_str[prev[nn1]]; nn1 = prev[nn1]; } cout<<"\n 所需走"<

} while(1); return 1; }

五．实验总结通过这次实验，了解到了选择算法的重要性，算法就像一个工具，它可以帮助我快速的解决问题。通过实践更加深了对上课所学知识的领会，能够灵活运用书本中的知识。不过同时暴露出了很多的问题，但我在今后的学习中会改进的。

分享到：

赞收藏

资料库

算法设计程序设计报告.doc

相关推荐

开发技术

热门标签

最新资料