资源描述：
《【精品】数学论文—图论》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。
1、最短路径的几种有效算法摘要：本文主耍描述无向简单图G的最短路径的3种有效算法，分别是生成树算法,Dijkstra算法以及Floyd算法，并用例题详细说明这些算法，而且尽可能清晰地证明了这3种算法的合理性。生成树算法和Dijkstra算法主要是求图G中某一固定顶点到其它顶点的最短路径，而Floyd算法算法只是求出了任意两顶点之间的距离，没有给出它们之间的最短路径。美屮不足的是木文没有找到实际例题，也没有把3种算法进行实质性的比较。关键词：生成树算法；Dijkstra算法；Floyd算法1前言31.1预备知识31.2基本概念32求顶点“°到其它顶点片的
2、最短路径的生成树算法42」生成树算法42.2应用42.3算法的说明52.4算法的证明63求顶点求顶点勺到其它顶点叫的最短路径的Dijkstra算法73.1Dijkstra算法73.2算法的说明73.3应用83.4算法的证明84求简单图G屮任意两顶点之间距离的Floyd算法94」两种运算94.3算法的说明104.4应用104.5Floyd算法的另一种表现形式104.6针对4.5算法的说明114.7针对4.5算法的证明11参考文献121前言1.1预备知识我们只须考虑无向简单图的最短路径问题。这是因为，若图G屮存在环，由于求两顶点Z间的最短路径，而环是连
3、接同一•顶点的边，它们Z间的距离为0,故环是多余的；若图G中存在多重边，则选取多重边中权最小的一条为边，这条边是连接两个端点的最短边，故为两端点的距离。在讨论最短路径算法之前，我们规定：图G中所有边的权为正的，图G的顶点数为“（G）（本文中有的地方也写作卩），墩为g（G）,边吧的权为巴•（若匕•，耳之间无边相连，则令叫二8）,匕•，耳之间的最短路径为q（如果存在多条，则选取其中的一条），v0,v,之间的最短路径为q,d“为顶点岭，专之间的距离。1.2基本概念定义1：图G中，若边£连接顶点"和v,贝聊尔"和v相邻，u和v是丘的两个端点,且比和"互为相
4、邻顶点；两个端点重合为一个端点的边称为环；若两个端点Z间连接不只一条边，则称其为多重边；若图G既没有环也没有多重边，则称图G为简单图,那么边《也可以表示为“。定义2：图G中一个顶点、边交替出现的且顶点互不相同的有限序列C=帕\e2v2...vk_xekvk（e.的两个端点分别是怙,片lWiWk）称为顶点v0到vk的一条路径，V。是路径C的始点，是路径C的终点；如果路径C的始点和终点相同，就称C为回路；如果图G屮任意两个顶点弘和"，G屮存在一条u到v的路径，则称G是连通图。定义3：若图T是连通图，且T中不含冋路，则称T是树，T上的边称为树枝；曲图G
5、的某些顶点及边构成的图称为图G的了图，即了图是图的一部分；若图G有一连通了图包含图G的全部顶点，且不含回路，称这样的子图为图G的生成树。不难证明，图T是树当且仅当图T连通，且g（T）=p（T）—1。定义4：给图G的每条边赋值，即构造一个函数w：e〜w（£）（幺是G的任一条边,w（e）称为边e的权;路径C的长度W（C）二w（勺）+w（d）+・・・+w（qj,即路径上所有边的权和；顶点u和卩之间的最短路径的长度称为u和卩之间的距离。在连通图G的所有生成树屮，所有边权和最小的生成树称为图G的最优生成树。破圈法：破圈法：设G是赋权连通图，若G不是树，则G中
6、必有凹路，我们删去含于某冋路中权最大的一条边（不改变图的连通性），得图G，q仍是赋权连通图;若q述有冋路，则继续下去，直至得到不含任何冋路的图7图T连通且不含冋路，则图T就是图G的最小生成树。2求顶点勺到其它顶点儿•的最短路径的生成树算法2.1生成树算法步骤⑴：任取连通简单图G的一棵生成树，并求点心到点叫的距离厶，在点叫旁边标上数值厶，替换匕・。设肝0,在点心旁边标上数值/。，替换I显然厶与生成树的选取有关，是生成树上点勺到点叫路径上各边的权和。步骤⑵：若对于图G中树枝以外的边时」,不等式->1广Wjj成立，则在选定的生成树中去掉以％•为顶点的树
7、枝，以边匕匕替代，并修改由此引起的路径长度的变化。步骤⑶：重复步骤⑵，直到对生成树以外的边都进行了比较，无任何变化为止，我们记最终所得树为T。在T中，对于树枝以外的任何边毗，都成立不等式101广w,,T中叫点对应的数值厶即为图G中顶点心到匕的距离，T中顶点卩。到％路径即为图G小顶点心到％的最短路径。2.2应用图12”3图4F面以Petersen图为例(图1),按此算法求顶点"。到V
8、图2—图5就是依据生成树算法进行的，图5上顶点"。到叫i(1
9、且只有一条路连接。因为树T是连通图，所以任意两个不同顶点之间有路连接。若在T中有两条路连接点u和卩，则这两条路的某些边可连
