第1页 / 共13页
第2页 / 共13页
第3页 / 共13页
第4页 / 共13页
第5页 / 共13页
第6页 / 共13页
第7页 / 共13页
第8页 / 共13页
交通咨询系统（数据结构课程设计报告+源代码）.doc
《数据结构》课程设计报告
实验五 图的设计
班
学
姓
级：
号：
名：
同 组 者：
时
间：
计升 091
090814101
王芙麟
无
一、设计目的与内容
1．设计目的
（1）．熟悉图的邻接链表存储结构。
（2）．熟悉图的邻接链表的建立。
（3）．掌握图的遍历算法。
（4）．熟练掌握迪杰斯特拉算法和费洛伊德算法，能够利用它们解决最短路径问题。
（5）．能够解决工程项目实施过程中的关键路径问题。
2．设计内容：
设计一个交通咨询系统,能让旅客咨询从任一个城市定点到另一个城市定点之间的最短路径
或最低花费或最少时间等问题。对于不同的咨询要求、可输入城市间的路程或所需时间或所
需花费。
要求：
（1）．建立交通网络网的存储结构。
（2）．提供程序测试方案。
（3）．界面友好。
二、 算法的基本思想
实验分三个部分，一是建立交通网络图的存储结构；二是解决单源最短路径问题；最后再实
现两个城市顶点之间的最短路径问题。
1． 建立图的存储结构
首先定义交通图的存储结构。邻接矩阵是表示图形中顶点之间相邻关系的矩阵。设 G=
（V，E）是具有 n 个顶点的图，则 G 的邻接矩阵是具有如下定义的 n 阶方阵。
A[i，j]=
Wij
0
或
vi
,
vj
)
或
(
，若
(
);
GE
。
，当不满足上述条件时
vi
,
vj
一个图的邻接矩阵表示是唯一的。图的邻接矩阵表示，除了需要用一个二维数
组存储顶点之间相邻关系的邻接矩阵外，通常还需要使用一个具有 n 个元素的一维
数组来存储顶点信息，其中下标为 i 的元素存储顶点 vi 的信息
2． 单源最短路径
初始化 S 和 D，置空最短路径终点集，置初始的最短路径值；
S[v1]=TRUE；D[v1]=0；//S 集初始时只有源点，源点到源点的距离为 0；
while（S 集中顶点数
虑从 vi 到 vj 是否包含有顶点 v2 为中间顶点的路径〈vi，…，v2，…，vj〉，若没有，
则说明从 vi 到 vj 的当前最短路径就是前一步求出的；若有，那么〈vi，…，v2，…，
vj〉可分解为〈vi，…，v2〉和〈v2，…，vj〉，而这两条路径是前一次找到的中间点序
号不大于 1 的最短路径，将这两条路径长度相加就得到路径〈vi，…，v2，…，vj〉的
长度。将该长度与前一次中求出的从 vi 到 vj 的中间顶点序号不大于 2 的最短路径。依
次类推，直至顶点 vn 加入当前从 vi 到 vj 的最短路径后，选出从 vi 到 vj 的中间顶点序
号不大于 n 的最短路径为止。由于图 G 中顶点序号不大于 n，所以 vi 到 vj 的中间顶点
序号不大于 n 的最短路径，已考虑了所有顶点作为中间顶点的可能性，因此，它就是
vi 到 vj 的最短路径。
三、测试数据
输入图中顶点个数和边数 n，e: 7,10
输入 10 条边的 i,j 及 w:
1,7,9
2,1,20
2,3,10
2,4,30
3,5,5
5,4,12
5,7,15
6,5,8
6,7,10
7,3,18
有向图的存储结构建立完毕!
******求城市之间的最短路径******
============================================
1.求一个城市到所有城市的最短路径
2.求任意的两个城市之间的最短路径
============================================
请选择: 1 或 2,选择 0 退出: 1
求单源路径,输入源点 v: 1
路径长度
路径
0
32767
27
44
32
32767
9
1
2
3<-7<-1
4<-5<-3<-7<-1
5<-3<-7<-1
6
7<-1
******求城市之间的最短路径******
============================================
1.求一个城市到所有城市的最短路径
2.求任意的两个城市之间的最短路径
============================================
请选择: 1 或 2,选择 0 退出: 2
dij=29,pij=1
dij=15,pij=3
dij=23,pij=3
dij=27,pij=3
dij=17,pij=5
dij=20,pij=5
dij=20,pij=5
dij=35,pij=3
dij=38,pij=3
dij=27,pij=7
dij=44,pij=7
dij=32,pij=7
dij=38,pij=5
dij=33,pij=7
dij=38,pij=7
dij=28,pij=7
输入源点(或称起点)和终点：v,w: 2,4
从顶点 2 到 4 的最短路径是: 2->3->5->4 路径长度: 27
******求城市之间的最短路径******
============================================
1.求一个城市到所有城市的最短路径
2.求任意的两个城市之间的最短路径
============================================
请选择: 1 或 2,选择 0 退出: 2
dij=29,pij=1
dij=15,pij=3
dij=23,pij=3
dij=27,pij=3
dij=17,pij=5
dij=20,pij=5
dij=20,pij=5
dij=35,pij=3
dij=38,pij=3
dij=27,pij=7
dij=44,pij=7
dij=32,pij=7
dij=38,pij=5
dij=33,pij=7
dij=38,pij=7
dij=28,pij=7
输入源点(或称起点)和终点：v,w: 1,4
从顶点 1 到 4 的最短路径是: 1->7->3->5->4 路径长度: 44
******求城市之间的最短路径******
============================================
1.求一个城市到所有城市的最短路径
2.求任意的两个城市之间的最短路径
============================================
请选择: 1 或 2,选择 0 退出: 0
输入图中顶点个数和边数 n，e: 7,20
输入 20 条边的 i,j 及 w:
1,2,2553
2,1,2553
1,3,695
3,1,695
1,4,704
4,1,704
2,3,511
3,2,511
2,5,812
5,2,812
3,4,349
4,3,349
3,6,1579
6,3,1579
4,7,651
7,4,651
5,6,2368
6,5,2368
6,7,1385
7,6,1385
有向图的存储结构建立完毕!
******求城市之间的最短路径******
============================================
1.求一个城市到所有城市的最短路径
2.求任意的两个城市之间的最短路径
============================================
请选择: 1 或 2,选择 0 退出: 1
求单源路径,输入源点 v: 1
路径长度
路径
0
1206
695
704
2018
2274
1355
******求城市之间的最短路径******
1
2<-3<-1
3<-1
4<-1
5<-2<-3<-1
6<-3<-1
7<-4<-1
============================================
1.求一个城市到所有城市的最短路径
2.求任意的两个城市之间的最短路径
============================================
请选择: 1 或 2,选择 0 退出: 2
dij=5106,pij=1
dij=3257,pij=1
dij=1390,pij=1
dij=3257,pij=1
dij=1408,pij=1
dij=5106,pij=2
dij=3365,pij=2
dij=1022,pij=2
dij=1323,pij=2
dij=4069,pij=1
dij=3365,pij=2
dij=1323,pij=2
dij=4069,pij=2
dij=1624,pij=2
dij=1390,pij=3
dij=1206,pij=3
dij=2018,pij=3
dij=2274,pij=3
dij=1206,pij=3
dij=1022,pij=3
dij=860,pij=3
dij=2090,pij=3
dij=860,pij=3
dij=698,pij=3
dij=1672,pij=3
dij=1928,pij=3
dij=2018,pij=2
dij=1672,pij=2
dij=2274,pij=3
dij=2090,pij=3
dij=1928,pij=3
dij=3158,pij=3
dij=1355,pij=4
dij=1511,pij=3
dij=698,pij=4
dij=1000,pij=4
dij=2323,pij=2
dij=1355,pij=4
dij=1511,pij=4
dij=1000,pij=4
dij=2323,pij=4
dij=1302,pij=4
dij=2770,pij=7
输入源点(或称起点)和终点：v,w: 5,7
从顶点 5 到 7 的最短路径是: 5->2->3->4->7 路径长度: 2323
******求城市之间的最短路径******
============================================
1.求一个城市到所有城市的最短路径
2.求任意的两个城市之间的最短路径
============================================
请选择: 1 或 2,选择 0 退出: 2
dij=5106,pij=1
dij=3257,pij=1
dij=1390,pij=1
dij=3257,pij=1
dij=1408,pij=1
dij=5106,pij=2
dij=3365,pij=2
dij=1022,pij=2
dij=1323,pij=2
dij=4069,pij=1
dij=3365,pij=2
dij=1323,pij=2
dij=4069,pij=2
dij=1624,pij=2
dij=1390,pij=3
dij=1206,pij=3
dij=2018,pij=3
dij=2274,pij=3
dij=1206,pij=3
dij=1022,pij=3
dij=860,pij=3
dij=2090,pij=3
dij=860,pij=3
dij=698,pij=3
dij=1672,pij=3
dij=1928,pij=3
dij=2018,pij=2
dij=1672,pij=2
dij=2274,pij=3
dij=2090,pij=3
dij=1928,pij=3
dij=3158,pij=3
dij=1355,pij=4
dij=1511,pij=3
dij=698,pij=4
dij=1000,pij=4
dij=2323,pij=2
dij=1355,pij=4
dij=1511,pij=4
dij=1000,pij=4
dij=2323,pij=4
dij=1302,pij=4
dij=2770,pij=7
输入源点(或称起点)和终点：v,w: 7,2
从顶点 7 到 2 的最短路径是: 7->4->3->2 路径长度: 1511
******求城市之间的最短路径******
============================================
1.求一个城市到所有城市的最短路径
2.求任意的两个城市之间的最短路径
============================================
请选择: 1 或 2,选择 0 退出: 0
四、源程序及系统文件使用说明
#include
#include
#define MVNum 100
#define Maxint 32767
enum boolean{FALSE,TRUE};
typedef char VertexType;
typedef int Adjmatrix;
typedef struct{
VertexType vexs[MVNum];
Adjmatrix arcs[MVNum][MVNum];
}MGraph;
int D1[MVNum],P1[MVNum];
int D[MVNum][MVNum],P[MVNum][MVNum];
void CreateMGraph(MGraph *G,int n,int e);
void Dijkstra(MGraph *G,int v1,int n);
void Floyd(MGraph *G,int n);
void main()
{ MGraph *G;
int m,n,e,v,w,k;
int xz=1;
G=(MGraph *)malloc(sizeof(MGraph));
printf("输入图中顶点个数和边数 n，e: ");
scanf("%d,%d",&n,&e);
相关推荐
2023年江西萍乡中考道德与法治真题及答案.doc
2012年重庆南川中考生物真题及答案.doc
2013年江西师范大学地理学综合及文艺理论基础考研真题.doc
2020年四川甘孜小升初语文真题及答案I卷.doc
2020年注册岩土工程师专业基础考试真题及答案.doc
2023-2024学年福建省厦门市九年级上学期数学月考试题及答案.doc
2021-2022学年辽宁省沈阳市大东区九年级上学期语文期末试题及答案.doc
2022-2023学年北京东城区初三第一学期物理期末试卷及答案.doc
2018上半年江西教师资格初中地理学科知识与教学能力真题及答案.doc
2012年河北国家公务员申论考试真题及答案-省级.doc
2020-2021学年江苏省扬州市江都区邵樊片九年级上学期数学第一次质量检测试题及答案.doc
2022下半年黑龙江教师资格证中学综合素质真题及答案.doc
