计算机应用与软件
計算機應用與軟件
계산궤응용여연건
COMPUTER APPLICATIONS AND SOFTWARE
2009年
9期
21-23,27
,共4页
最短路问题%位势法%增广链%弧割
最短路問題%位勢法%增廣鏈%弧割
최단로문제%위세법%증엄련%호할
给出最短路问题的数学模型,根据线性规划的对偶原理提出了最短路问题的两种位势法.这两种算法的计算思路均为:从确定一个起点势和标准势开始;再用标准势与已确定最短路的顶点势进行比较,按照势的由小到大顺序逐步得到其他顶点的势和路由,每次迭代要更新标准势;直到找到终点的势和路由为止.两种算法采用不同的标准势计算法.一种采用原标准势累加1的更新法,该算法仅适用于正整数费用网络;另一种利用弧割的概念寻找最小标准势来代替原标准势,该算法适用于正费用情形.证明了算法的正确性以及为说明算法的有效性给出了一个算例.最后通过与Dijkstra算法的比较分析了位势法的五条特点,得出结论:位势法是求解最短路问题的有效算法.
給齣最短路問題的數學模型,根據線性規劃的對偶原理提齣瞭最短路問題的兩種位勢法.這兩種算法的計算思路均為:從確定一箇起點勢和標準勢開始;再用標準勢與已確定最短路的頂點勢進行比較,按照勢的由小到大順序逐步得到其他頂點的勢和路由,每次迭代要更新標準勢;直到找到終點的勢和路由為止.兩種算法採用不同的標準勢計算法.一種採用原標準勢纍加1的更新法,該算法僅適用于正整數費用網絡;另一種利用弧割的概唸尋找最小標準勢來代替原標準勢,該算法適用于正費用情形.證明瞭算法的正確性以及為說明算法的有效性給齣瞭一箇算例.最後通過與Dijkstra算法的比較分析瞭位勢法的五條特點,得齣結論:位勢法是求解最短路問題的有效算法.
급출최단로문제적수학모형,근거선성규화적대우원리제출료최단로문제적량충위세법.저량충산법적계산사로균위:종학정일개기점세화표준세개시;재용표준세여이학정최단로적정점세진행비교,안조세적유소도대순서축보득도기타정점적세화로유,매차질대요경신표준세;직도조도종점적세화로유위지.량충산법채용불동적표준세계산법.일충채용원표준세루가1적경신법,해산법부괄용우정정수비용망락;령일충이용호할적개념심조최소표준세래대체원표준세,해산법괄용우정비용정형.증명료산법적정학성이급위설명산법적유효성급출료일개산례.최후통과여Dijkstra산법적비교분석료위세법적오조특점,득출결론:위세법시구해최단로문제적유효산법.
