![](https://csdnimg.cn/release/download_crawler_static/18809120/bg1.jpg)
第
44
卷第
7
期
2012
年
7
月
哈尔滨工业大学学报
JOURNAL OF HARBIN
INSτ1TUTE
OF TECHNOLOGY
VoL
44
No.7
July
2012
经典
Bellman-Ford
算法的改进及其实验评估
韩伟一
(哈尔滨工业大学经济与管理学院,
150001
哈尔滨)
摘
要:针对以高效求解有边数限制的最短路问题,对经典
Bellman-Ford
算法进行了改进.借鉴划分算法的
思想,通过减少距离标号的数目,得到了两个改进算法.既然已有的改进算法均不能解决有边数限制的最短
路问题,因而本算法是经典
Bellman-
F
ord
算法的全新改进.相对于经典
Bellman-Ford
算法,改进后的算法不
仅可有效地节省存储空间,而且实验表明能显著地提高计算效率.
关键词:算法
Bellman-Ford
算法;划分算法;最短路问题
中图分类号:
1
回
0
1.
6
文献标志码
:A
文章编号
:0367
-6234(2012)07
-0074-04
Im
provement and experimental evaluation on
c1
assical
Bellman-
Ford
algorithm
HAN Wei-yi
(School
of
Economic
and
Management
,
Harbin
Institute
of
Technology
,
150001
Harbin
, China)
Abstract:
Classical Bellman-Ford algorithm is improved
to
solve the shortest path prohlem with bounded edge
numher efficiently. Using the experience of partitioning algorithm for reference
,
two
improved algorithms are
ohtained, which can decrease the numher of distance lahels of vertices. Since all existing improved Bellman-
Ford algorithms
can'
t solve the shortest path prohlem with hounded edge number, these
two
improved algo-
rithms are entirely new. In contrast to the common version of Bellman-Ford algorithm , these two improved al-
gorithms can save storagé space efficiently
, and can raise computing efficiency remarkahly.
Key
words:
algorithm; Bellman-Ford algorithm; partitioning algorithm; the shortest path prohlem
Bellman -
Ford
算法一般有两种表述,一种为
经典的动态规划模式或经典算法
[1
-3]
另外一种
为划分模式或划分算法(
Pa
此
itioning
algo-
由
hm)[4-
7J
.严格意义上,划分算法并不是普遍公
认的经典
Bellman-Ford
算法,而是经过改进的
Bellman-Ford
算法,它把参与第
i
轮和第
i
+
1
轮
迭代的点进行了明确划分,改进了距离标号的计
算方式,能够显著提高计算效率.目前,采用先进
先出策略的划分算法是解决负权最短路问题、最
短路问题可行性问题的最有竞争力的算法,在算
法基础上再加人门槛技术即成为解决负权最短路
收稿日期:
2012
-04
-0
1.
基金项目:国家自然科学基金资助项目
(70672063
)
;哈尔滨工业
大学青年优秀基金资助项目
(2009036)
.
作者简介:韩伟一
(1974
一)
,男,博士,讲师.
通信作者:韩伟一.
wyhan@
mails.
gucas.
ac.
cn.
问题当前公认的最快算法
[8
-9]
尽管经典的
Bell
mqn-Ford
算法在解决负权最短路问题、最短路问
题可行性问题已经不具有优势,但它仍然是解决
有边数限制最短路问题的最好算法
[IO-II]
本文将
研究经典
Bellman-Ford
算法及其性质,并将对之
进行改进,使之能更快地解决有边数限制最短路
问题,同时将对改进后的算法进行实验评估.
1
经典
Bellman-Ford
算法的两种形
式及其性质
对于一个具有
n
个点、
m
条边的有向图
G(V
,
E)
,
n
个点分别以
1
,
2
,…
,
n
为编号,且规定点
1
为始点,
ω
(i
,
j)
为有向边
(i
,
j)
的权.定义
dk(i)
为
点
i
在第
k
次迭代后
i
点的距离标号,则可给出经
典
Bellman-Ford
算法的常见形式为:
Step
1
初始化.令
d
o
(1 ) = 0 , d
o
(i)
=