实验课程名称数据结构课程设专业班级10级计科（1）班学生姓名陈志军学号10410901036指导教师冯韵2012至2013学年第1学期第1至9周目录TOC\o"1-3"\u1概述PAGEREF_Toc338245656\h32系统分析PAGEREF_Toc338245657\h32.1设计要求及分析PAGEREF_Toc338245658\h32.2设计分块PAGEREF_Toc338245659\h33概要设计PAGEREF_Toc338245660\h43.2设计模块PAGEREF_Toc338245661\h43.1.1建立图的存储结构PAGEREF_Toc338245662\h43.1.2单源最短路径PAGEREF_Toc338245663\h43.1.3任意一对顶点间最短路径PAGEREF_Toc338245664\h53.2程序流程图PAGEREF_Toc338245665\h64详细设计PAGEREF_Toc338245666\h64.1建立有向图的存储结构PAGEREF_Toc338245667\h64.2迪杰斯特拉算法PAGEREF_Toc338245668\h74.3费洛伊德算法PAGEREF_Toc338245669\h84.4运行主控程序PAGEREF_Toc338245670\h94.5源程序代码PAGEREF_Toc338245671\h105运行与测试PAGEREF_Toc338245672\h136总结与心得PAGEREF_Toc338245673\h161概述在交通网络非常发达、交通工具和交通方式不断更新的今天，人们在出差、旅游或做其他出行时，不仅关心节省交通费用，而且对里程和所需时间等问题也感兴趣。对于这样一个人们关心的问题，可用一个图结构来表示交通网络系统，利用计算机建立一个交通咨询系统。图中顶点表示城市，边表示城市之间的交通关系。这个交通系统可以回答旅客提出的各种问题。例如，一位旅客要从A城到B城，他希望选择一条途中中转次数最少的路线。假设图中每一站都需要换车，那么这个问题反映到图上就是要找一条从顶点A到B所含边的数目最少的路径。我们只需要从顶点A出发对图作广度优先搜索，一旦遇到顶点B就终止。由此所得广度优先生成树上，从根顶点A到顶点B的路径就是中转次数最少的路径。路径上A与B之间的顶点就是路径的中转站数，但只是一类最简单的图的最短路径问题。2系统分析2.1设计要求及分析设计一个交通咨询系统，能让旅客咨询从任一个城市顶点到另一城市顶点之间的最短路径（里程）或最低花费或最少时间等问题。对于不同咨询要求，可输入城市间的路程或所需时间或所需费用。2.2设计分块该设计共分三个部分，一是建立交通网络图的存储结构；二是解决单源最短路径问题；最后再实现两个城市顶点之间的最短路径问题。1.建立图的存储结构要实现设计要求，首先要定义交通图的存储结构。邻接矩阵是表示图形中顶点之间相邻关系的矩阵。设G＝(V,E)是具有n个顶点的图，则G的邻接矩阵是具有如下定义的n阶方阵。wij,若（vi,vj）或<vi,vj>∈E（G）A[i,jl=0或∞，当不满足上述条件时一个图的邻接矩阵表示是唯一的。图的邻接矩阵表示，除了需要用一个二维数组存储顶点之间相邻关系的邻接矩阵外，通常还需要使用一个具有n个元素的一维数组来存储顶点信息，其中下标为i的元素存储顶点vi的信息。因此，图的邻接矩阵的存储结构定义如下：#definfMVNum5。／／最大顶点数typedefstruct｛VertexTypevexs［MVNum］：／／顶点数组，类型假定为char型Adjmatrixarcs[MVNum][MVNum];／／邻接矩阵，假定为in七型}MGraph；2.单源最短路径3.任意一对顶点间最短路径3概要设计3.2设计模块设计一个交通咨询系统，能让旅客咨询从任一个城市顶点到另一城市顶点之间的最短路径（里程）或最低花费或最少时间等问题。对于不同的咨询要求，可输入城市间的路程或所需时间或所需费用。本设计共分三部分，一是建立交通网络图的存储结构；二是解决单源最短路径问题；三是实现任两个城市顶点之间的最短路径问题。3.1.1建立图的存储结构邻接矩阵是表示图形中顶点之间相邻关系的矩阵。图的邻接矩阵是定义如下的n阶方阵：设G=（V，E）是一个图，结点集为。G的邻接矩阵当邻接矩阵的行表头、列表头顺序一定时，一个图的邻接矩阵表示是唯一的。图的邻接矩阵表示，除了需用