资源描述：
《关于最短路径的SPFA快速算法》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、第卷第期西南交通大学学报年月丫·关于最短路径的快速算法段凡丁西南交通大学计算中心成都【摘要】本文提出了关于最短路径问题的一种新的快速算法,—即算法算法采用动态优化逼近的方法用邻接表作为有向图的存储结,。。构用了一个先进先出的队列归来作为待优化点的存储池算法的时间复杂性为,在绝大多数情况下,图的边数。和顶点数的关系是。矛,因此,算法比经典的创归算法在时间复杂性方面更优越【关键词】有向图最短路径算法时间复杂性【分类号】甲、、,在计算机网络交通运输工程通信工程等各种应用中常常需要计算图中从某个源点到其余各顶点的最短路径或各顶点之间的最短路径。很多的优化问题在数学上讲,
2、是相当于找寻,,。一个图中的最短路径因此在图论中最短路径算法比其它算法研究得更为透彻到年,。,为止大约有多篇论文和几十种算法已经提出来了关于单源最短路径的算法目前最,。,流行的经典算法是算法它的时问复杂性是口矿〕峨年采用桶分类得。,。出一个口的算法但必须是边的权值是小的整数才适用关于每一对顶点之间的最短路,,。。〕。径算法公认算法最佳其时间复杂性为本文对最短路径问题的这两个方面,,口。,。妒,进行研究提出了一种新的快速算法算法的时问复杂性为当《时—。,算法表现出时问复杂性上的优越算法对边的权值没有特殊的限制适合于任意有向图。单源最短路径的算法如算法分析,为了清楚
3、起见和便于比较现将算法简述如下。。刀。。〔〕,。一。。。。。,。〔〕,护本文于年月收到。西南交通大学学报第卷’不一〔。〕功卜’一。,,。,刀〕创〔〕算法采用了两个集合这样的数据结构来安排图的顶点。算法的主要思想是从有一,,向图的集合中选取具有最小」的点尔后把点放入集合中那么集合就是已经。。然后再从卜集合中将所有经过点。而与源点相通的点的计算出具有最短路径的点的集合。。,。。路径值〕统统都作调整如果存在」十的话重复此过程直到所有的点全部进入集合。,,一从以分析可以看出算法属于探新法的一种即每次都是从集合中选一个,。具有最小「。的点并放入集合进入了集合的点的路径值就
4、保证是该点的最短路径算法是一步一个脚印地向前搜索,即循环的每一步都能正确地算出从源点到。点的最短路,一。径「并且将所有的经过点的集合的点的路径值都作相应的优化从时问仁来分,忍,,,。,,析若有个顶点的图则第句为第句为。这两项是并列在循环里的。,,。。而循环也是。故总的时为简算为数量级算法描述输人设是用来表示有向图,的邻接表,邻接表元素是有向图各边的权值,输入各边的权值,建立邻接表。,输出设数组是记录当前从源点到其余各点的最短路径的值初始化时数组的每个元素都为最大值,经过算法数组输出各点的最短路径值。方法算法采用图的存储结构是邻接表,方法是动态优化逼近法。算法中设
5、立了一,,个先进先出的队列用来保存待优化的顶点优化时从此队列里顺序取出一个点并且用,,,点的当前路径「去优化调整其它各点的路径值「月若有调整即「月的值改小了就将点放入队列以待继续进一步优化。反复从队列里取出点来对当前最短路,,径进行优化直至队空不需要再优化为止此时数组里就保存了从源点到各点的最短路径值。算法的形式算法描述及注释如下算法开始’砂不无〔。,无读入每条边的权值到邻接表。」初始化每个顶点是否在队里的标志数组,〔第期段凡丁关于最短路径的快速算法将最短路径数组初始化为最大值。。〔〕。。源点人队。。〔源点到源点本身的路径值赋值为零从队列里取出一个点,,咬,点出
6、队后其标志数组元素改为零表示点不在队列,任。」,夕,〕〕,刀,。,哎判断经过点到少点的路径是比原来的路径刀「月更短后,对点的路径进行优化〕夕〕,,当点不在队列里,入队并且将「月标志置为表示已入队不,〕咬优化完成后,,数组存放的就是从源点到各点的最短路径值可以输出结果算法结束算法的正确性证明对算法的正确性,要证明以下两个定理。定理算法采用的动态优化方法,能够使得数组的路径值变得越来越小,优化西南文通大学学报第卷过程是正确的,,证算法中采用了一个正的优化顺序队用来存放待优化的点算法中每一步都是从该队取出点来优化其它各点。现假定算法结束时计算的结果不是最短路径,即从源
7、点,,到某些点还存在着更短的路径而算法规定只要存在着比姚月更短的路径即月死司,,,力那么刀月就一定要被优化且,点就要入队算法就不会结束见算法第句至第。,,句所以上述假定不成立算法的执行会使刀数组的值变得越来越小通进直至达到最短路径,优化过程正确。,,。定理算法的优化过程是收敛的不会形成无限循环算法能够正常结束证算法,而是直接从尽管不是从队列里去挑选出具有最小路径的点来进行优化,二,队列里取出队首的点来进行优化因此整个优化过程不一定循环次就能完成有些点入队次,,,,数也可能不止一次那么是否存在不收敛的情况呢众所周知在有向图中各边的。,只要,权值都是已知的并且在整个
8、算法中是不会改变的可以证
