郑州轻工业学院 实 训 报 告
实训名称： 求城市之间最短路径
姓 名： 院 （系）：软件学院 专业班级：信息安全 学 号：************
指导教师：
成 绩：
时间： 2010 年 6 月 14 日至 2010 年 6 月 18 日
郑州轻工业学院软件学院
实训任务书
一、题目
求城市之间最短路径
二、实训的性质和任务
通过本次实训，对这个学期学习的知识进行巩固，加深对课本知识的理解，拉近课本知识与实际应用的距离。
三、实训的基本要求 四、实训内容及要求
天/日期 6－11 6－12 6－13 6－14 任务描述 需求分析，构建框架 结构体，图的邻接矩阵，弗洛伊德算法的实现 程序代码完成，编译运行成功 编写实训报告，实验验收 通过标准 完成流程图 系统各部件完成 程序功能基本实现 程序报告上传 五、考核指标及成绩评定
实训成绩由下面构成：
平时成绩（10%）+作品（70%）+实训报告（20%）=总评成绩 作品成绩评定标准： 1、全部完成90-100 2、主要功能完成70-90 3、部分功能完成60-70 4、少部分完成40-60 5、几乎没做0-40
完 成 期 限： 2010 年 6 月 18 日 指导教师签章： 专业负责人签章： 教学院长签章
2010年 6 月 18 日
郑州轻工业学院软件学院
2009－2010学年第二学期 数据结构 课程实训教学工作总结表
指导教师 专业班数、人数、周数 王治国 信息安全08－2班、53人、一周 实训题目：求城市之间最短路径
实训组织形式及过程管理： 通过指导老师的分配，不同的学生分到了不同的项目。同学集中在一起，在指导老师的辅助和同学之间的相互帮助下完成自己的实训项目。 实训总结： 由于个人水平有限，这个城市最短路径系统的功能还比较简单，还有一些好的设想没有实现：比如添加管理模式，使得个人能够同样方便的更改图中信息，因此更改这路径图还必须在程序员的帮助下进行。另外，系统还有一定的局限性，算法上还有缺陷，根据各种信息求最短路径的算法太过麻烦，根据老师的指导应用结构来设计。系统的这些不足请老师多多谅解。今后我会更多的学习数据结构的相关知识，更深刻地理解图的基本操作，不断提升认识，提高编程技巧，借以不断地提高程序设计水平。 成绩评定及分析 存在问题： 对结构体的理解还不够深刻，图的邻接矩阵的建立也不够熟练，弗洛伊德算法也只是停留在看的懂的阶段，真正让自己写程序代码，还有一定困难。 指导教师： 王治国 日期： 2010-6-18
说明：1、实训结束二周内将此表送至教务处实践教学管理科。 2、要求：纸质、电子文档各一份。
郑州轻工业学院软件学院
2009－2010学年 二 学期 实训教学日历
题求城市之间最短路径 目 指导教师 王治国 学生班级 信息安全08－2班 实训学时 32学时 时上午/实训分解任任务描述（解决方案、实现步骤、技术路线、难点通过标提示） 准 间 下午 务 6 月 11 日 6 月12 日 6月17日 6上 午 下 午 上 午 下 午 上 午 下 午 需求分析 分析此系统具体需要实现什么功能，可能会用到已学习的哪些知识 罗列出了各种需求，必要知识 流程图完成 完成邻接矩阵的建立 算法实现 构建框架 努力实现程序流程图 建立结构体，图的邻接矩阵是一个难点，建立邻接矩阵不难，而图的邻接矩是难在邻接矩阵到算法的转化 阵 最关键步骤的失现 弗洛伊德算法的实现 程序整体要基本完成 代码基本完成 编译运行成功 对程序进行完善 细节部分优化 界面更加友好，功能得到优化 实训报告完成 上 午 编写实训报告 对近段时间的工作加以总结 月18日 下 午 程序报告上传 实验验收，对自己近段工作评价 上传完成
制订教师： 王治国 日期：2010-6-18
一、 需求说明
编写程序帮助旅游者找出从一个城市到另一个城市的最短旅行路径。
该程序应该读取一个包含了一个城市列表和一个连接城市的路径列表的数据文件。每个城市信息包含城市名称、城市级别（首都、直辖市、省会、地极市、县级市），每条路径包含两城市之间的距离、最低费用、最少花费时间。
二、 功能描述
能进行城市信息的修改； 能进行城市之间路径的修改； 能按满足不同用户的查询，如自费旅游的人希望费用最省，因公出差的人希望花费时间最少，自己开车出行的人希望距离最短等。
三、 系统设计及实现
在程序中首先要对数据源进行初始化，建立图的邻接矩阵，然后用弗洛伊德算法进行最短路径的计算，输出各个城市之间的最短路径，算法主要内容还是最短路径算法的设计，以及读取数据建立图的邻接矩阵的方法。核心中的核心还是弗洛伊德算法。
要完成对整个城市最短路径系统的功能实现，需要对的每一项功能都有清楚的设想和认识，了解并明确每一项功能的实现需要解决的问题，选择正确并且高效的算法把问题逐个解决，最终实现程序的正确调试运行。
为此，可把系统分为以下几个核心：读取数据、图的初始化、求两点间的最短路径、求最佳路线。
（一）读取数据及图的初始化
这是整个系统中非常重要的一部分。这一步骤的实现，只需建立一个邻接矩阵，将城市和路径信息输入即可。这是实现所有操作的基础，其存储结构将直接影响到程序的实现的难易度、空间性能和时间性能，综合各方面考虑，选择邻接矩阵。
（二） 弗洛伊德算法求最短路径
基于本程序中图的存储是邻接矩阵结构存储的图结构，因而采用适合该存储结构的弗洛伊德算法用于解决求最短路径的问题。
Floyd-Warshall算法（Floyd-Warshall algorithm）是解决任意两点间的最短路径的一种算法，可以正确处理有向图或负权的最短路径问题。
Floyd-Warshall算法的时间复杂度为O(N3)，空间复杂度为O(N2)。 Floyd-Warshall算法的原理是动态规划。
设Di,j,k为从i到j的只以(1..k)集合中的节点为中间结点的最短路径的长度。
若最短路径经过点k，则Di,j,k = Di,k,k − 1 + Dk,j,k − 1； 若最短路径不经过点k，则Di,j,k = Di,j,k − 1。
因此，Di,j,k = min(Di,k,k − 1 + Dk,j,k − 1,Di,j,k − 1)。
在实际算法中，为了节约空间，可以直接在原来空间上进行迭代，这样空间可降至二维。
Floyd-Warshall算法的描述如下： for k ← 1 to n do for i ← 1 to n do for j ← 1 to n do
if (Di,k + Dk,j < Di,j) then Di,j ← Di,k + Dk,j;
其中Di,j表示由点i到点j的代价，当Di,j为 ∞ 表示两点之间没有任何连接。
（三）各步骤实现情况
1.查看已有城市信息
2.查看已有路径信息（部分）
3.修改城市信息 修改前：
修改：
修改后：
4.修改路径信息
5.查询最佳路径
实训心得
由于我水平有限，这个城市最短路径系统的功能还比较简单，还有一些好的设想没有实现：比如添加管理模式，使得个人能够同样方便的更改图中信息，因此更改这路径图还必须在程序员的帮助下进行。另外，系统还有一定的局限性，算法上还有缺陷，根据各种信息求最短路径的算法太过麻烦，根据老师的指导应用结构来设计。系统的这些不足请老师多多谅解。今后我会更多的学习数据结构的相关知识，更深刻地理解图的基本操作，不断提升认识，提高编程技巧，借以不断地提高程序设计水平。
五 附录代码
#include #define INFINITY 10000 #define MAX_VERTEX_NUM 20 #define MAX 40 typedef struct ArCell { int adj[3]; }ArCell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; typedef struct { char name[30]; int num; char introduction[100]; }infotype; typedef struct { infotype vexs[MAX_VERTEX_NUM]; AdjMatrix arcs; int vexnum,arcnum; }MGraph; MGraph b; void cmd(void); MGraph InitGraph(void); void Menu(void); void Menu2(void); void Browser(MGraph *G); void alterc(MGraph *G); void Floyd(MGraph *G,int m); void alterl(MGraph *G); void print(MGraph *G); void main(void) { cmd(); } void cmd(void) { int i; b=InitGraph(); Menu(); scanf(\"%d\ while(i!=6) { switch(i) { case 1:system(\"cls\");Browser(&b);Menu();break; case 2:system(\"cls\");print(&b);Menu();break; case 3:system(\"cls\");Browser(&b);alterc(&b);Menu();break; case 4:system(\"cls\");Browser(&b);print(&b);alterl(&b);Menu();break; case 5:system(\"cls\");Browser(&b);print(&b);Menu2();break; case 6:exit(1);break; default:break; } scanf(\"%d\ } } MGraph InitGraph(void) { MGraph G; int i,j; G.vexnum=6; G.arcnum=15; for(i=0;i strcpy(G.vexs[0].introduction,\"省会\"); strcpy(G.vexs[1].name,\"商丘\"); strcpy(G.vexs[1].introduction,\"地级市\"); strcpy(G.vexs[2].name,\"洛阳\"); strcpy(G.vexs[2].introduction,\"地级市\"); strcpy(G.vexs[3].name,\"北京\"); strcpy(G.vexs[3].introduction,\"首都\"); strcpy(G.vexs[4].name,\"济南\"); strcpy(G.vexs[4].introduction,\"省会\"); strcpy(G.vexs[5].name,\"登封\"); strcpy(G.vexs[5].introduction,\"县级市\"); for(i=0;i G.arcs[0][1].adj[0]=200; G.arcs[0][2].adj[0]=300; G.arcs[0][3].adj[0]=600; G.arcs[0][4].adj[0]=230; G.arcs[0][5].adj[0]=240; G.arcs[1][2].adj[0]=250; G.arcs[1][3].adj[0]=600; G.arcs[1][4].adj[0]=270; G.arcs[1][5].adj[0]=280; G.arcs[2][3].adj[0]=650; G.arcs[2][4].adj[0]=320; G.arcs[2][5].adj[0]=330; G.arcs[3][4].adj[0]=580; G.arcs[3][5].adj[0]=590; G.arcs[4][5].adj[0]=180; G.arcs[0][1].adj[1]=40; G.arcs[0][2].adj[1]=150; G.arcs[0][3].adj[1]=190; G.arcs[0][4].adj[1]=90; G.arcs[0][5].adj[1]=20; G.arcs[1][2].adj[1]=50; G.arcs[1][3].adj[1]=230; G.arcs[1][4].adj[1]=70; G.arcs[1][5].adj[1]=80; G.arcs[2][3].adj[1]=200; G.arcs[2][4].adj[1]=20; G.arcs[2][5].adj[1]=130; G.arcs[3][4].adj[1]=190; G.arcs[3][5].adj[1]=210; G.arcs[4][5].adj[1]=80; G.arcs[0][1].adj[2]=60; G.arcs[0][2].adj[2]=100; G.arcs[0][3].adj[2]=160; G.arcs[0][4].adj[2]=40; G.arcs[0][5].adj[2]=50; G.arcs[1][2].adj[2]=50; G.arcs[1][3].adj[2]=200; G.arcs[1][4].adj[2]=70; G.arcs[1][5].adj[2]=20; G.arcs[2][3].adj[2]=210; G.arcs[2][4].adj[2]=30; G.arcs[2][5].adj[2]=60; G.arcs[3][4].adj[2]=190; G.arcs[3][5].adj[2]=190; G.arcs[4][5].adj[2]=80; for(i=0;i return G; }//城市和路径数据源初始化 void Menu() { printf(\"\\n printf(\" \\n\"); printf(\" \\n\"); printf(\" \\n\"); printf(\" \\n\"); printf(\" 求城市最短路径\\n\"); 1.查看已有城市信息 2.查看已有路径信息 3.修改城市信息 4.修改路径信息 5.查询最佳路径 \\n\"); printf(\" 6.退出系统 \\n\"); printf(\"菜单号-:\"); } void Menu2() { int i; printf(\"\\n 请选择\\n\"); printf(\" 1.自费旅游 \\n\"); printf(\" 2.因公出差 \\n\"); printf(\" 3.自己开车出行 \\n\"); printf(\"菜单号-:\"); scanf(\"%d\ while(i!=4) { switch(i) { case 1:system(\"cls\");Browser(&b);Floyd(&b,0);Menu();break; case 2:system(\"cls\");Browser(&b);Floyd(&b,1);Menu();break; case 3:system(\"cls\");Browser(&b);Floyd(&b,2);Menu();break; default:break; } break; } } void Browser(MGraph *G) { int v; printf(\" 编号 城市名称 简介 \\n\"); for(v=0;v //输出城市列表 void Floyd(MGraph *G,int m) { int v,u,i,w,k,j,flag=1,p[10][10][10],D[10][10]; for(v=0;v D[v][w]=G->arcs[v][w].adj[m]; for(u=0;u if(D[v][w] for(u=0;u p[v][w][i]=p[v][u][i]||p[u][w][i]; } while(flag) { printf(\"请输入出发点和目的地的编号:\"); scanf(\"%d%d\ if(k<0||k>G->vexnum||j<0||j>G->vexnum) { printf(\"城市编号不存在!请重新输入出发点和目的地的编号:\"); scanf(\"%d%d\ } if(k>=0&&k printf(\"%s\ for(u=0;u printf(\"-->%s\ printf(\"-->%s\ switch(m) { case 0: printf(\" 最短距离为%dm\\n\ case 1: printf(\" 最少费用为%d$\\n\ case 2: printf(\" 最短时间为%ds\\n\ } }//弗洛伊德算法 void alterc(MGraph *G) { int k,flag=1; while(flag) { printf(\"请输入要修改的城市编号:\"); scanf(\"%d\ if(k<0||k>G->vexnum) { printf(\"城市编号不存在!请重新输入城市编号:\"); scanf(\"%d\ } if(k>=0&&k printf(\"请输入新的城市名：\"); scanf(\"%s\ printf(\"请输入该城市的级别：\"); scanf(\"%s\ printf(\"修改成功！\"); } //城市修改 void alterl(MGraph *G) { int k,j,m,flag=1; while(flag) { printf(\"请输入待修改路径相连的两个城市编号:\"); scanf(\"%d%d\ if(k<0||k>G->vexnum||j<0||j>G->vexnum) { printf(\"城市编号不存在!请重新输入:\"); scanf(\"%d%d\ } if(k>=0&&k printf(\"请依次输入新路径的距离，费用和时间：\\n\"); for(m=0;m<3;m++) { scanf(\"%d\ G->arcs[j][k].adj[m]=G->arcs[k][j].adj[m]; } } //路径修改 int LocateVex(MGraph *G,char* v) { int c=-1,i; for(i=0;i if(strcmp(v,G->vexs[i].name)==0) {c=i;break;} return c; } void print(MGraph *G) { int v,w,t=0; printf(\" 城市 距离 费用 时间\\n\" ); for(v=0;v for(w=0;w if(G->arcs[v][w].adj[0] //输出两地路径 因篇幅问题不能全部显示，请点此查看更多更全内容