文档介绍：上海电机学院
课程设计报告
学 院：电子信息学院
专业：网络工程
姓 名：唐章武
班 级: BX1213
指导老师：堂艳
报告日期：2013年12月11日
年月制
目录
一、 需求分析： 1
二、 总体结构设计： 1
三、 各子模块设计： 2
四、 编程实现： 3
五、 测试结果： 6
六、 总结： 9
七、 参考文献： 9
九、附录源代码： 10
一、需求分析:
设计一程序，完成交通咨询系统的设计。旅客咨询从任一个城市顶点到另一个城市顶 点之间的最短路径或最低费用或最少时间等问题。对于不同咨询要求，可以输入城市间的路 程或所需要时间或所需费用。可用实例来验证迪杰斯特拉算法。要求“
建立交通网络图的存储结构；
解决单源最短路径问题；
实现两个城市顶点之间的最短路径问题。
要求： 根据以上功能说明，设计程序完成功能。
二、总体结构设计：
输入不同数字，来控制程序执行不同的子模块并实现相应功能。
三、各子模块设计:
，按要求输入城市名字、边数以及各边权值
新建城市网
/i命入顶点数及边数。
输入各边权值(路程，费用，时间)+
分别输入n±城市的名字3
返回主菜单
，咨询权值分别为路程、时间、费用的最短路径
四、编程实现：
鉴于实际生活中交通网络的双向性，特建立无向网来说明各城市间的交通关系。
#include<>
#include<>
#include<>
#define MAXLEN 100
#define INFINITY 99999 〃定义一个很大的数，邻接矩阵边的初始权值
〃图的邻接矩阵存储结构如下：
typedefstruct
charvexs[MAXLEN] [MAXLEN];
float edges_path[MAXLEN][MAXLEN]; 〃以路径为边的权值
float edges_money[MAXLEN][MAXLEN]; 〃以费用为边的权值
float edges_time[MAXLEN] [MAXLEN]; 〃以时间为边的权值
intn,e;
JMGraph;
〃建立一个无向图的邻接矩阵存储的算法简略如下:
MGraph *CreateMGraph()
{
inti,j,k;
floatweight_path,weight_money,weight_time;
char chi[MAXLEN],ch2[MAXLEN];
MGraph *G;
G=(MGraph *)malloc(sizeof(MGraph));
//邻接矩阵初始化
for (i=0; i<G->n; i++)
for (j=0; j<G->n; j++)
{
G->edges_path[i] [j]=INFINITY;
G->edges_money[i] [j]=INFINITY;
G->edges_time[i] [j]=INHNITY;
}
〃给无向图的边赋初值
for(i=0;strcmp(chl ,G->vexs[i]) !=0; i++);
for(j=0;strcmp(ch2,G->vexs [j])!=0; j++);
(
G->edges_path [i] [j ] = weight_path;
G->edges_path[j] [i]=weight_path;
G->edges_money[i][j]=weight_money;
G->edges_money[j][i]=weight_money;
G->edges_time[i] [j ]=weight_time;
G->edges_time[j] [i]=weight_time;
〃函数功能，找到城市名字在邻接矩阵中对应的下标
intTranform_Name_int(MGraph *G,char vO_Name[],char vl_Name[] ,int&vO,int &vl)
//vO为起始顶点在邻接矩阵顶点数组中的下标。
//P为二维的布尔矩阵类型，矩阵P用来存储当前已经求得的所有最短路径；
〃若P[v][w]为true,则w是当前求得的从vO到v最短路径上的顶点
//D为浮点型型数组类型，数组D用来存储从vO到所有顶点的带权路径长度
〃用Dijkstra算法求无向网G的vO顶点到其余顶点v的最短路径p[v]