基于Dijkstra算法的一类最长路问题的一种改进算法

李宝凤，郝璞玉



基于Dijkstra算法的一类最长路问题的一种改进算法

李宝凤，郝璞玉

（唐山师范学院 数学与信息科学系，河北 唐山 063000）

目前认为Dijkstra算法是求解指定两点间或从指定点到其余各点无负权网络最短路问题的最好方法，但不能求解最长路问题。提出一种改进算法，求解最长路问题，并给出一个实例说明该算法的正确性。

最长路；设备更新；Dijkstra算法改进

1 引言

求解最长路问题有多种方法，如动态规划、逐步逼近算法、路矩阵算法等。Dijkstra算法被认为是求解指定两点间或从指定点到其余各点无负权网络最短路问题的最好方法，也有根据实际情况对Dijkstra算法提出一些改进算法[1-2]，用于求解最短路问题。本文以设备更新为例，提出先把最长路问题转化为最短路问题，然后用Dijkstra算法求解的新思路。

2 最长路问题算法改进

改进算法：

3 算例

设某台新设备的年效益及年均维修费、更新净费用如表1所示。试确定今后5年内的更新策略，使总收益最大。

表1 年效益r(t)、维修费u(t)、更新费c(t)

图1 计算边上的数字过程示意图

图2 重新计算边上的数字过程示意图

令

计算

则

则

则

则

则

（5）总效益为

4 结论

[1] 王智广,王兴会,李妍.一种基于Dijkstra最短路径算法的改进算法[J].内蒙古师范大学学报(自然科学版), 2012,41(2):195-200.

[2] 何成刚,杨维平,杨光,等.基于改进Dijkstra算法的最短路算法[J].价值工程,2015,(15):204-206.

[3] 胡运权,郭耀煌.运筹学教程(第三版)[M].北京:清华大学出版社,2007:218-219.

An Improved Algorithm of Longest Paths Based on Dijkstra Algorithm

LI Bao-feng, HAO Pu-yu

(Department of Mathematics and Information Science, Tangshan Normal University, Tangshan 063000, China)

Now the Dijkstra algorithm is thought as the best way to solve problems of the shortest road without negative network, which are to specify two points or from the specified point to the remaining points. However it can’t be applied to solve problems of the longest road. In this paper An improved adaptive algorithm is proposed and an example is given to illustrate the correctness of the algorithm.

longest road; equipment replacement; Dijkstra algorithm improvement

O228

A

1009-9115(2019)03-0035-02

10.3969/j.issn.1009-9115.2019.03.009

2018-01-24

2018-11-07

李宝凤（1971-），女，河北唐山人，硕士，副教授，研究方向为计算数学、运筹学。

（责任编辑、校对：赵光峰）