基于Dijkstra算法的一類最長路問題的一種改進算法

李寶鳳，郝璞玉

?

基于Dijkstra算法的一類最長路問題的一種改進算法

李寶鳳，郝璞玉

（唐山師范學院 數(shù)學與信息科學系，河北 唐山 063000）

目前認為Dijkstra算法是求解指定兩點間或從指定點到其余各點無負權網(wǎng)絡最短路問題的最好方法，但不能求解最長路問題。提出一種改進算法，求解最長路問題，并給出一個實例說明該算法的正確性。

最長路；設備更新；Dijkstra算法改進

1 引言

求解最長路問題有多種方法，如動態(tài)規(guī)劃、逐步逼近算法、路矩陣算法等。Dijkstra算法被認為是求解指定兩點間或從指定點到其余各點無負權網(wǎng)絡最短路問題的最好方法，也有根據(jù)實際情況對Dijkstra算法提出一些改進算法[1-2]，用于求解最短路問題。本文以設備更新為例，提出先把最長路問題轉化為最短路問題，然后用Dijkstra算法求解的新思路。

2 最長路問題算法改進

改進算法：

3 算例

設某臺新設備的年效益及年均維修費、更新凈費用如表1所示。試確定今后5年內的更新策略，使總收益最大。

表1 年效益r(t)、維修費u(t)、更新費c(t)

圖1 計算邊上的數(shù)字過程示意圖

圖2 重新計算邊上的數(shù)字過程示意圖

令

計算

則

則

則

則

則

（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-），女，河北唐山人，碩士，副教授，研究方向為計算數(shù)學、運籌學。

（責任編輯、校對：趙光峰）