一、设计目的与内容
1．设计目的
（1）．熟悉图的邻接链表存储结构。
（2）．熟悉图的邻接链表的建立。
（3）．掌握图的遍历算法。
（4）．熟练掌握迪杰斯特拉算法和费洛伊德算法，能够利用它们解决最短路径问题。
（5）．能够解决工程项目实施过程中的关键路径问题。
2．设计内容：
设计一个交通咨询系统,能让旅客咨询从任一个城市定点到另一个城市定点之间的最短路径
或最低花费或最少时间等问题。对于不同的咨询要求、可输入城市间的路程或所需时间或
所需花费。
要求：
（1）．建立交通网络网的存储结构。
（2）．提供程序测试方案。
（3）．界面友好。
二、 算法的基本思想
实验分三个部分，一是建立交通网络图的存储结构；二是解决单源最短路径问题；最后再
实现两个城市顶点之间的最短路径问题。
1． 建立图的存储结构
首先定义交通图的存储结构。邻接矩阵是表示图形中顶点之间相邻关系的矩阵。设
G=（V，E）是具有 n 个顶点的图，则 G 的邻接矩阵是具有如下定义的 n 阶方阵。
A[i，j]=
一个图的邻接矩阵表示是唯一的。图的邻接矩阵表示，除了需要用一个二维数组存
储顶点之间相邻关系的邻接矩阵外，通常还需要使用一个具有 n 个元素的一维数
组来存储顶点信息，其中下标为 i 的元素存储顶点 vi 的信息
2． 单源最短路径
初始化 S 和 D，置空最短路径终点集，置初始的最短路径值；
S[v1]=TRUE；D[v1]=0；//S 集初始时只有源点，源点到源点的距离为 0；
while（S 集中顶点数<n）
{
开始循环，每次求得 v1 到某个 v 顶点的最短路径，并加 v 到 S 集中；
S[v]=TRUE；
更新当前最短路径及距离；
}
3． 任意一对顶点间最短路径
假设求从顶点 vi 到 vj 的最短路径。如果从 vi 到 vj 存在一条长度为 arcs[i][j]的路径，该
路径不一定是最短路径，还需要进行 n 次试探。首先考虑路径〈vi，v1〉和〈v1，vj〉
是否存在。如果存在，则比较路径〈vi，vj〉和〈vi，v1，vj〉的路径长度，取长度较
