第 2 1 卷 第 4 期 地 球 物 理 学 进 展 Vol. 21 No. 4
2006 年 12 月
(
页码 :1120～1126
)
PRO GRESS IN GEOPH YSICS Dec. 2006
弯曲射线追踪中 Dijkstra 算法的改进与实现
王汪根
1
, 刘盛东
2
, 张平松
2
(
1. 中国地质大学
(
北京
)
地球科学与资源学院 , 北京 100083 ; 2. 安徽理工大学资源与环境工程系 ,淮南 232001
)
摘 要 文章针对图论中寻找最短路径的 Dijkstra 算法内存占用量大 ,效率低的缺点 ,对该算法进行了改进 ,修改后
的算法计算效率是原来的四倍 ,内存使用量和图中节点数呈线性关系. 在此基础上 ,用新算法求出了激发点和接收点
的最短走时路径 ,并由激发接收点的旅行时结合联合迭代法对理论模型和实际场地进行了反演. 结果表明 :和直射线
追踪相比 ,弯曲射线路径能更好地反演出地质体内部的速度场分布. 理论模型和实际探测结果证实改进后的算法是
有效的.
关键词 Dijkstra 算法 ,弯曲射线 ,射线追踪 ,反演
中图分类号 P315 文献标识码 A 文章编号 100422903
(
2006
)
0421120207
The improvement and implementation of the Dijkstra
algorithm in bending ray tracing
WAN G Wang2gen
1
, L IU Sheng2dong
2
, ZHAN G Ping2song
2
(
1. School of the Earth Sciences and Resourses , China University of GeoSciences
(
Beijing
)
, Bei j ing 100083 , China;
2. Department of Rresources and Envi ronmental Engineering , A nhui University of Science and Technology , Huainan 232001 , China
)
Abstract The Dijkstra algorithm which was used in searching the shortest path in graph theory has some defects such
as taking much memory , bad efficiency , etc. In this paper , the Dijkstra algorithm was ameliorated. The efficiency of
the new algorithm is four times higher than that of the old algorithm , and the relationship between memory used by
new method and the number of nodes in graph is linear. Based on this method , the shortest parth of traveling time be2
tween the shot and receiver was calculated , and the velocity fields of an academic modal and an actual field were recon2
structed by the simultaneous iterative reconstruction technique. The results indicated that the velocity distributing of
geology body can be reconstructed better with the bending ray path than with the straight ray path. Theoretical model
and the result of practical prospection prove that the new method is effective.
Keywords dijkstra algorithm ,bending ray ,ray tracing ,inversion
收稿日期 2005211210 ; 修回日期 2006203220.
基金项目 国家自然科学基金项目
(
40573033
)
、国家自然科学基金项目
(
40173021
)
和安徽省自然科学基金项目
(
03044403
)
联合资助.
作者简介 王汪根 ,1982 年生 , 男 ,安徽省潜山县人 ,2004 年毕业于安徽理工大学资源与环境工程系 ,目前在中国地质大学
(
北京
)
攻读硕士
学位 ,地球探测与与信息技术专业
(
E2mail :wwgen @126. com
)
.
0 引 言
基于 射 线 理 论 的 层 析 成 像
(
Computerized
tomography
)
的关键技术之一是求激发点到接收点
的射线路径问题 ,即射线追踪. 射线追踪又可分为直
射线追踪和弯曲射线追踪. 直射线追踪层析成像适
合于比较均匀的介质
[1 ]
,而在实际的地质勘查中 ,地
质体一般为波速差异较大的非均匀介质 ,这时用直
射线追踪反演误差较大 ,所以一般采用弯曲射线追
踪. 目前 的 弯 曲射线追 踪 方 法 有 多 种 , 如 : 试 射
法
[2 ,3 ]
、基于求解程函方程的有限差分法
[4 ]
、有序波
前法
[5 ,6 ]
和基于费马原理的最短路径法
[7～15 ]
等.
文中主要讨论的是基于费马原理的最短路径法
射线追踪技术. 这种方法是先将探测空间用网格离
散化 ,然后在网格边上设置一定的节点 ,射线路径就
由这些 点 相 互 连 接 而 成. 1986 年 , Nakanishi 和
Yamaguci
[7 ]
首先将图论中查找最短路径的 Dijkstra
算法用于中最小走时路径射线追踪 ,此后 Moser
[8 ]
、
Cao
[9 ]
和 Klimes
[10 ]
等对此法的性能做了详细的评
价. 国内也有很多学者将此法应用于实践并对其做
