最短路问题的位势法

• 作者: 同小军 周康 高婧
• 来源期刊: 计算机应用与软件
• 学科: 工学
• 关键词: 最短路问题 位势法 增广链 弧割
• 年，卷（期）: 2009,（9）
• 所属期刊栏目: 基金项目论文
• 页码范围: 21-23,27
• 页数: 4页
• 分类号: TP3
• 字数: 5227字
• 语种: 中文
• DOI: 10.3969/j.issn.1000-386X.2009.09.007

摘要

给出最短路问题的数学模型,根据线性规划的对偶原理提出了最短路问题的两种位势法.这两种算法的计算思路均为:从确定一个起点势和标准势开始;再用标准势与已确定最短路的顶点势进行比较,按照势的由小到大顺序逐步得到其他顶点的势和路由,每次迭代要更新标准势;直到找到终点的势和路由为止.两种算法采用不同的标准势计算法.一种采用原标准势累加1的更新法,该算法仅适用于正整数费用网络;另一种利用弧割的概念寻找最小标准势来代替原标准势,该算法适用于正费用情形.证明了算法的正确性以及为说明算法的有效性给出了一个算例.最后通过与Dijkstra算法的比较分析了位势法的五条特点,得出结论:位势法是求解最短路问题的有效算法.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	周康	武汉工业学院数理科学系	69	557	14.0	20.0
3	同小军	武汉工业学院数理科学系	28	317	11.0	17.0
9	高婧	武汉工业学院数理科学系	3	7	1.0	2.0