| 适用于动态有向图路径检索的一种数据结构 |
| |
| 引用本文： | 肖大海,陈亮.适用于动态有向图路径检索的一种数据结构[J].华中科技大学学报(自然科学版),1994(1). |
| |
| 作者姓名： | 肖大海 陈亮 |
| |
| 作者单位： | 华中理工大学数控中心 |
| |
| 摘 要： | 给出一种表达加权有向图的数据结构，它使得对此有向图进行“插入”操作后，只需进行Ｏ（ｎ２）时间的维护工作，就可使得每对结点间的最短路径迅速地得到修整。
|
| 关 键 词： | 有向图 路径 数据结构 |
A New Type of Data Structure for the Path Search of Dynamic Digraphs |
| |
| Xiao DahaiNumerical Control Center,H.U.S.T.,Wuhan ,China.,Chen Liang.A New Type of Data Structure for the Path Search of Dynamic Digraphs[J].JOURNAL OF HUAZHONG UNIVERSITY OF SCIENCE AND TECHNOLOGY.NATURE SCIENCE,1994(1). |
| |
| Authors: | Xiao DahaiNumerical Control Center HUST Wuhan China Chen Liang |
| |
| Institution: | Xiao DahaiNumerical Control Center,H.U.S.T.,Wuhan 430074,China.,Chen Liang |
| |
| Abstract: | To meet the frequent requirement for finding the shortest path and the length betweenevery pair of nodes in a dynamic weighted digraph,a new type of data structure has been de-veloped.With the new data structure,when a new weighted edge is to be inserted in a cur-rent digraph, only O(n2)time of maintenance is needed to re-obtain the shortest paths;Suchadata structure can also be used to meet similar operation requirements in ordinary non-di-rected graphs and it is useful in the maintenance of dynamic networks. |
| |
| Keywords: | digraph path data structure |
| 本文献已被 CNKI 等数据库收录！ |
