数据结构与算法
课程设计
一、问题描述及设计目的
城市公共交通最短线路，利用邻接矩阵来构建交通节点，邻接矩 阵的行列编号即为交通中的节点，有行列决定的数据即为权值 基本的输入信息和条件：
1.输入总的节点个数，即为交通中的站点数目
本程序中，站点的数目最大值为100。
2.输入存在的通路，即为弧两个站点之间是联通的
弧的数目是有限制的，数目小于站点数目[n *( n-1)]/2
3.输入存在通路的两点，即为两站点
站点编号要小于站点总数目
二、    应具备的功能
1.确定起点的最短路径问题，即已知起始结点，求最短路径的问题。
2.确定终点的最短路径问题，与确定起点的问题相反，该问题是已 知终结结点，求最短路径的问题。在无向图中该问题与确定起点的 问题完全等同，在有向图中该问题等同于把所有路径方向反转的确 定起点的问题。
3.确定起点终点的最短路径问题，即已知起点和终点，求两结点之 间的最短路径。
三、    设计思想、主要算法的实现、基本操作、子程序调 用关系
1.Dijkstra算法的基本思想
按路径长度递增顺序求最短路径算法。
2.Dijkstra算法的基本步骤
设V。是起始源点，数据结构与算法分析答案S是已求得最短路径的终点集合。
V-S =未确定最短路径的顶点的集合，    初始时S={V 0}，长度最短的路
径是边数为1且权值最小的路径。
下一条长度最短的路径：
①Vi • V - S，先求出Vo到Vi中间只经S中顶点的最短路径；
② 上述路径中长度最小者即为下一条长度最短的路径;
② 将所求最短路径的终点加入 S中；
重复直到求出所有终点的最短路径。
3.存储结构设计
本系统采用图结构类型（mgraph）存储抽象交通图的信息。其中: 各站点间的邻接关系用图的邻接矩阵类型存储；图的顶点个数及边的 个数由分量n、e表示，它们是整型数据。
数据结构如下:
int no;
typedef struct
//顶点编号
的权值



版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。