Dijkstra矩阵算法1
需积分: 0 117 浏览量
2022-08-04
16:30:36
上传
评论
收藏 184KB PDF 举报
文章编号 : 1004 - 6011
(
2007
)
02 - 0065 - 03
Dijkstra 矩阵算法
代西武
(
北京建筑工程学院 基础科学部 , 北京 100044
)
摘 要 : 介绍了 Dijkstra 算法 ,对 Dijkstra 算法进行改进 ,提出了计算加权图中任意两点之间最短
距离的算法 ———Dijkstra 矩阵算法 ,给出了 Dijkstra 矩阵算法在 Matlab 语言中的实现 ,对一个具体
例子 ,应用 Dijkstra 矩阵算法进行了验算.
关键词 : Dijkstra 算法 ; 最短路问题 ; 最短距离 ; 矩阵 ; Matlab 语言
中图分类号 : O151121 文献标识码 : A
Dijkstra’s Matrix Algorithm
Dai Xiwu
(
Dept. of Basic Sciences , BUCEA Beijing 100044
)
Abstract : In this paper , the Dijkstra’s algorithm is introduced. By improving Dijkstra’s algorithm ,
the Dijkstra’s matrix algorithm , which is to calculate the shortest distance between two arbitrary
vertexes in a weighted graph is proposed. The MATLAB source code of Dijkstra’s matrix algorithm is
supplied , and an example is calculated.
Key words: dijkstra’s algorithm ; shortest path problem ; shortest distance ; matrix ; matlab
收稿日期 : 2007 - 01 - 05
作者简介 : 代西武
(
1963 -
)
,男 ,副教授 ,研究生 ,研究方向 :图论、计算机科学、数学建模.
在图论中 ,Dijkstra 算法
[1 ]
是很实用的 ,可以用
来计算加权图里的两个指定顶点 u
0
与 v
0
之间的
最短距离 , 实际上 ,Dijkstra 算法计算出了从 u
0
到
其它所有顶点的最短距离. 在实际问题中 , 经常需
要计算加权图中任意两个顶点之间的最短距离 ,为
此 ,我们对 Dijkstra 算法进行了改进 , 提出了 Dijk2
stra 矩阵算法 ,该算法比 Dijkstra 算法更容易在计算
机上实现 ,能够计算加权图中任意两个顶点之间的
最短距离 , 方便实用. 进一步 , 我们用 Matlab 编出
了 Dijkstra 矩阵算法的源程序 ,并对一个例子 ,进行
了计算 ,得出了满意的结果.
1 Dijkstra 算法
已知图 G
(
V , E
)
及每条边的权 w
(
e
)
,对于任
意指定的二点 u
0
、v
0
∈V
(
G
)
,寻找路 P
(
u
0
, v
0
)
,
使得
w
(
P
(
u
0
, v
0
) )
= min
P ∈
Ω
{ w
(
P
)
}
其中
Ω
是从 u
0
到 v
0
的所有路的集合 , w
(
P
)
是路 P 上的各边权之和. 这样的路 P
(
u
0
, v
0
)
称为
从 u
0
到 v
0
的最短路 , w
(
P
(
u
0
, v
0
) )
称为从
u
0
到
v
0
的最短路的长度 ,也可称为从 u
0
到 v
0
的最短距
离. Dijkstra 算法可以计算出从 u
0
到其它所有顶点
的最短距离.
下面介绍 Dijkstra 算法
[1 ]
:
(
1
)
:置 l
(
u
0
)
= 0 ; 对 v ≠u
0
, 置 l
(
v
)
= ∞;
S
0
= { u
0
} ; i = 0;
(
2
)
: 对每个
v ∈/ S
i
, 用 min { l
(
v
)
,
l
(
u
i
)
+
w
(
u
i
v
)
}代替 l
(
v
)
. 计算min
v ∈/ S
i
{ l
(
v
)
} , 并把达到这
第 23 卷 第 2 期
2007 年 6 月
北 京 建 筑 工 程 学 院 学 报
Journal of Beijing University of Civil Engineering and Architecture
Vol. 23 No. 2
Jun. 2007
王者丶君临天下
- 粉丝: 18
- 资源: 265
最新资源
- 基于ARM的指令调度和延迟分支
- 基于Vue和TypeScript的极简聊天应用设计源码 - HasChat
- 基于Vue2全家桶和Zcool数据的图片收集网站设计源码 - cool-picture
- 基于C和C++的二维绘制工具设计源码 - DrawPro
- Object.defineProperty 的 IE 补丁object-defineproperty-ie-master.zip
- 整卷预览.mhtml
- MySQL是一种广泛使用的开源关系型数据库管理系统，它提供了丰富的SQL语句用于数据库的创建、查询、更新和管理 以下是一些常见的
- MySQL是一种广泛使用的开源关系型数据库管理系统，它提供了丰富的SQL语句用于数据库的创建、查询、更新和管理 以下是一些常见
- MySQL是一种广泛使用的开源关系型数据库管理系统，它提供了丰富的SQL语句用于数据库的创建、查询、更新和管理 以下是一些常见的
- 基于Javascript的结婚请帖设计源码 - Invitation
资源上传下载、课程学习等过程中有任何疑问或建议，欢迎提出宝贵意见哦~我们会及时处理！
点击此处反馈
评论0