【摘 要】
：
给出最短路问题的数学模型,根据线性规划的对偶原理提出了最短路问题的两种位势法。这两种算法的计算思路均为:从确定一个起点势和标准势开始;再用标准势与已确定最短路的顶
【机 构】
：
武汉工业学院数理科学系,华中科技大学控制科学与工程系
【基金项目】
：
国家自然科学基金项目(60403002);湖北省自然科学基金项目(2007ABA407);湖北教育厅重点教研项目(20040248)
论文部分内容阅读
给出最短路问题的数学模型,根据线性规划的对偶原理提出了最短路问题的两种位势法。这两种算法的计算思路均为:从确定一个起点势和标准势开始;再用标准势与已确定最短路的顶点势进行比较,按照势的由小到大顺序逐步得到其他顶点的势和路由,每次迭代要更新标准势;直到找到终点的势和路由为止。两种算法采用不同的标准势计算法。一种采用原标准势累加1的更新法,该算法仅适用于正整数费用网络;另一种利用弧割的概念寻找最小标准势来代替原标准势,该算法适用于正费用情形。证明了算法的正确性以及为说明算法的有效性给出了一个算例。最后通过与Dijkstra算法的比较分析了位势法的五条特点,得出结论:位势法是求解最短路问题的有效算法。
其他文献
企业变革带来企业各种生产关系的调整,企业变革期是企业发展规范整顿的重要机遇期,也是企业与社会各类矛盾集中交汇的特殊时期。如何在企业变革期理顺关系,维持稳定,是企业领
大卫·库伯把体验学习分为具体体验、反思观察、抽象概括及行动应用四个环节,符合高职思想政治理论课程实践教学的实际和需要。我们应提高对体验学习的认识,并从这四个环节入
余园位于北京东城东厂胡同,原为清代大学士瑞麟的宅园。此园规模很大,建筑密度较小,而且基本上集中于东南一区,西部则为大片空地,体现出文人园疏朗朴素的气质。园中设有八角
电视是儿童社会化的重要载体,电视节目对儿童成长的意义重大。以社会学视角观之,电视节目的城市化倾向对农村儿童的成长有特殊的影响。作为特殊受众的农村儿童,极易对城市化
中华优秀文化是中华民族实现伟大复兴的精神力量,是激励全党全国各族人民奋勇前进的强大动力.提升文化自信,需在坚持社会主义发展方向的基础上厚植理论力量、传统力量、道路
《社会信用体系建设规划纲要（2014——2020）》明确提出了全国社会信用体系建设的原则与目标,并对社会信用体系的建设做出了规划。在金融业,信用是金融业生态环境的一个重要的要
为保证基础设施即服务(IaaS)模式云环境中资源的有效分配与高效调度,提出了一种基于集成模型-优化神经网络的资源需求预测方法(EMONN).分析了用户偏好以及资源配置需求,根据
在我国科研评价体系的影响下,高校综合性学报普遍面临学术质量下滑的困境。多数高校学报已经不能代表本校的科研水平,不再是展示本校科研实力的窗口。《北京工商大学学报(自
传统教学观念把知识看成是定论 ,把学习看成是知识从外到内的输入 ,同时低估了学习者的认知能力、知识经验及其差异性 ,并在教学中表现出了过于简单化的倾向。这些教学观念上
提出了一种基于二次曲面拟合的插值算法。该算法对最近邻插值算法中的阶梯状直边界起很好的平滑作用,有效地解决了线性插值算法中的亮度损失问题,避免了高阶插值算法运算量巨