基于改进的Kruskal算法求解最短路程问题.doc

提供完整版的毕业设计研究生综合应用报告课程名称高级计算机网络学院计算机学院年级一专业班学生姓名张仲勋学号20141402024开课时间2014至2015学年第一学期基于流媒体的高清视频传输摘要本文使用适当改进的Kruskal算法，解决为使总路程最短如何选择出行路线的问题。把要到访的地点作为顶点，所有顶点两两之间的连线和距离（起点和终点无连线）分别作为边以及边的权值，构造加权无向图。问题即转化为寻求从起点出发，遍历中间各点，最后到达终点的最短路径。该路径是无向图的生成树，但不一定是最小生成树。路径的起点和终点已经固定，他们的度数必须为1，而中间各顶点的度数必须为2，原因在问题分析里面进行说明。通过对Kruskal算法适当改进可以得到该路径。关键词：最短路径生成树Kruskal算法问题分析对于该类问题，要先得到任意两个地点之间的距离，因为不能直接从起点到达终点，所以不需要知道起点和终点的直接距离，也即在其加权图上这两点之间没有边。可以通过百度地图[1]等工具获取两个地点的距离。由于路径的起点和终点固定，起点只能“出去”，终点只能“进来”，当求其最短路径时，这两个点的度数要为1。对于起点和终点之外的其他顶点，其度数只能为2，原因如下：对于任意三个顶点（起点和终点除外）A、B、C，假如A的度数为3（大于3时只考虑和A相临的其中两点），如图1所示。图1：一点的度数大于2设A先到B点，要经过C点的话必须回到A，再到C，其路程必然比从B直接到C远。这种情形也包含某个点的度数为1的情况，所以除起点和终点外其他顶点的必为2。综上所述，在改进Kruskal算法时，只需加上两个限制条件即可，即起点的度数为1，其余顶点度数为2。模型建立把每个地点作为顶点，每两个顶点相连作为边，两个顶点之间的距离作为边的权值，构造加权无向图，如图2所示（单位：千米）。其中a代表重庆，b代表五台山，c代表黄鹤楼，d代表泰山，e代表北京，。由于不能从出发点直接到达终点，所以a到e没有连线。图2：路线模型图符号说明：存放生成树的边的集合，初态为空集；：生成树的权值，初值为零；VS：部分树的顶点集的集合，初值为：{{a}，{b}，{c}，{d}，{e}}；：顶点的度数。Kruskal算法改进Kruskal算法步骤[2]：=1\*GB3①←Ø，←0，VS←{{a}，{b}，{c}，{d}，{e}}，将边按权值小到大排成队列Q；=2\*GB3②若=1，输出，，停止。否则转入下一步；=3\*GB3③从Q中取出边，并从Q中删除；=4\*GB3④如果u，v在VS的同一个元素中，则转=3\*GB3③，否则分属两个集合，，进入下一步；=5\*GB3⑤←∪{}，←∪，VS←VS–{}–{}+，←+，转入=2\*GB3②。由问题分析可知，在对Kruskal算法进行改进时，只需添加两个限制条件，起点和终点的度数为1，其余各点度数为2。引入来表示顶点的度数，初值为0，把Kruskal算法的第=4\*GB3④步改为如下形式：如果u，v在VS的同一个元素中，或者(，u，v不是起点或终点)，或者(，u，v是起点或终点)，则转=3\*GB3③，否则u，v分属两个集合，，←+1，←+1，进入下一步。五、问题求解使用改进的Kruskal算法求图2的最小生成树，按边的权值从小到大排列为：，，，，，，，，，步骤如下：选出边，得到={}，=359，VS={{}，{}，{}，{}}；←+1=1；←+1=1；选出边，由于的度只能为1，重新选边；选出边，由于b，d分属VS的两个不同的集合，=1，=0，故得到={，}，VS={{}，{a}，{c}}，=359+576=935，←+1=2，←+1=1；选出边，由于c，d分属VS的两个不同的集合，=0，=1，故得到={，，}，VS={{}，{a}}，=935+863=1798，←+1=1，←+1=2；选出边，由于a，c分属VS的两个不同的集合，=0，=1故得到={，，，}，VS={{}}，=1798+896=2694，←+1=1，←+1=2；因=1，输出={，，，}，=2694，计算停止。的图形如图2所示，即是通过改进的Kruskal算法求得的最小生成树。图2：最短路线图由图2可知，当如下安排行程：重庆到黄鹤楼，黄鹤楼到泰山，泰山到五台山，五台山到北京，此时总的路程最短，为2694公里。参考文献[1]百度地图：http://map.baidu.com/[2]龚劬，图论与网络最优化算法，重庆：重庆大学出版社，2009年10月第一版0464260785065428107602181011605595730725603177074080080195369461899217073530783654523528725306509406