西南交大赵宏宇数据结构课程设计

1、数据结构课程设计北京至其他省会城市的最短路径班级：计科2014-04班姓名：宋思雨学号：2014112024 日期：2016年6月21日一课程设计任务描述：建立教材图7.33（中国省会城市交通网）的数据文件，构建邻接矩阵存储结构。以北京为始点，求出北京到其他城市的最短路径。结果输出到字符文件保存。二算法要点描述使用迪杰斯特拉算法求最短路径。按路径长度递增次序产生算法：把顶点集合V分成两组：（1）S：已求出的顶点的集合（初始时只含有源点V0）（2）V-S=T：尚未确定的顶点集合将T中顶点按递增的次序加入到S中，保证：（1）从源点V0到S中其他各顶点的长度都不大于从V0到T中任何顶点的最短路径长度

2、（2）每个顶点对应一个距离值S中顶点：从V0到此顶点的长度T中顶点：从V0到此顶点的只包括S中顶点作中间顶点的最短路径长度依据：可以证明V0到T中顶点Vk的，或是从V0到Vk的直接路径的权值；或是从V0经S中顶点到Vk的路径权值之和（反证法可证）求最短路径步骤算法步骤如下：G=V,E1. 初始时令 S=V0,T=V-S=其余顶点，T中顶点对应的距离值若存在，d(V0,Vi)为弧上的权值若不存在，d(V0,Vi)为2. 从T中选取一个与S中顶点有关联边且权值最小的顶点W，加入到S中3. 对其余T中顶点的距离值进行修改：若加进W作中间顶点，从V0到Vi的距离值缩短，则修改此距离值重复上述步骤2、3

3、，直到S中包含所有顶点，即W=Vi为止三源程序代码#include stdafx.h#include #include #include #include using namespace std;typedef enum UDG,DGNetTp;#define MAX_N 30/定义数组最大值#define INFINITY 999999/定义无穷大typedef struct int n,e;NetTp tp;int wMAX_NMAX_N;ALNet;int distMAX_N;vector pathMAX_N;char cityMAX_NMAX_N=北京,天津,郑州,呼和浩特,沈阳,徐州

4、,武汉,西安,兰州,乌鲁木齐,西宁,成都,株州,上海,大连,长春,哈尔滨,南昌,广州,柳州,贵阳,昆明,南宁,深圳,福州;void SP(ALNet &G,int k,int dist,vector path)/迪杰斯特拉算法int i,j,m;set S;for(i=0;iG.n;i+)/初始化各终点距离始点路径长度disti=G.wki;if(disti!=INFINITY)pathi.push_back(k);pathi.push_back(i);for(m=0;mG.n-1;m+)/按长度递增次序生成各终点最短路径for(j=0;jG.n;j+)if(j!=k & S.find(j)=

5、S.end()break;/判断j点是否已经计算过 最短路径for(i=j+1;iG.n;i+)if(i!=k & distidistj & S.find(i)=S.end() j=i;S.insert(j);for(i=0;id)disti=d;pathi=pathj;pathi.push_back(i);void create(ALNet &G)/初始化邻接矩阵fstream f1(data.txt);/打开文件f1G.nG.e;/写入顶点数n和边数eint i=0,j;while(iG.n)/初始化各边权重为无穷大j=0;while(jij;f1G.wij;G.wji=G.wij;i=0

6、;int main(int argc, char* argv)ALNet G;int i=1;int j=0;G.tp=UDG;/初始化为无向图create(G);/初始化无向网SP(G,j,dist,path);/迪杰斯特拉算法fstream file(out.txt);/打开要输出的文件while(i25)/输出最短路径到指定文件中filecity0到cityi的最短路径是：;for(j=0;i!=pathij;j+)filecitypathij-;filecityi;fileendl;i+;return 0;四输出结果输入：输出：五问题与讨论1.迪杰斯特拉算法的计算各终点最短路径不包括始点本身，怎样修改加入？答：修改i！=k； 循环由n-1次改为n次