文档下载 文档下载导航
设为首页 | 加入收藏
搜索 请输入内容:  
 导航当前位置: 文档下载 > 所有分类 > 高等教育 > 理学 > A Note on Two Problems in Connexion with Graphs
侵权投诉

A Note on Two Problems in Connexion with Graphs

A Note on Two Problems in Connexion with Graphs,By E.W.DIJKSTRA.介绍完毕

Numerische Mathematik~, 269--271 (1959)

A Note on T w o Problems in Connexion with Graphs By

E. W. DIJKSTRA We consider n points (nodes), some or all pairs of which are connected by a branch; the length of each b r a n c h is given. We restrict ourselves to the case where at least one p a t h exists between any two nodes. We now consider two problems.

Problem 1. Constrnct the tree of minimum total length between the n nodes. (A tree is a graph with one and only one path between every two nodes.) In the course of the construction that we present here, the branches are subdivided into three sets: I. the branches definitely assignec~ to the tree under construction (they will form a subtree); II. the branches from which the next branch to be added to set I, will be selected; I I I . the remaining branches (rejected or not yet considered). The nodes are subdivided into two sets: A. the nodes connected b y the branches of set I, B. the remaining nodes (one and only one branch of set of these nodes), We start the construction b y choosing an arbitrary node of set A, and b y placing all branches t h a t end in this node with, set I is empty. From then onwards we perform the repeatedly.

I I will lead to each as the only member in set II. To start following two steps

Step 1. The shortest branch of set I I is removed from this set and added to set I. As a result one node is transferred from set B to set A. Step 2. Consider the branches leading from the node, t h a t has just been transferred to set A, to the nodes t h a t are still in set B. If the b r a n c h under consideration is longer than the corresponding branch in set I I, it is rejected; it it is shorter, it reptaces the corresponding branch in set I i, and the latter is rejected. We then return to step I and repeat the process until sets I I and]3 are empty. The branches in set I form the tree required. The solution given here is to be preferred to the solution given b y J . B . KRUSKAL[1] and those given b y H. LOBERMAN and A. WEINBERGER[2]. In their solutions all the -- possibly 89 -- branches are first of all sorted according to length. Even if the length of the branches is a computable function of the node coordinates, their methods demand that d a t a for all branches are stored simultaneously. Our m e t h o d only requires the simultaneous storing of Numbs. N a t h . B d . 4. i9

A Note on Two Problems in Connexion with Graphs

第1页

你可能喜欢

热门文档

相关文档

  • 基于插值A算法的路径规划

    //bbs.elecfans.com 电子技术论坛 基于插值 A*算法的路径规划 吕太之 1, 赵...A note on two problems in connexion with graphs. Numerische Mathematik,1:...

  • 地标导向的启发式路径规划算法

    的启发式路径规划算法摘要:为提高大规模交通网络路径规划算法的查询效率,以 a ?...a note on two problems in connexion with graphs 〔j〕. numerische ...

  • On line graphs and road networks

    W. (1959), ‘A note on two problems in connexion with graphs’. Numerische Mathematik 1, p. 269–271. Jiang J., Han H. and Chen J. (2002),...

  • 图论和网络分析算法及Matlab实现(Graph and Network An...

    (1959). A note on two problems in connexion with graphs. Numerische Mathematik 1, 269–271. ? 原理: Bellman最优化原理 若P是网络G中从Vs到Vt 的一条...

  • Dijkstra算法

    W. Dijkstra: A note on two problems in connexion with graphs. In: Numerische Mathematik. 1 (1959), S. 269–271 Thomas H. Cormen, Charles E. ...

  • 268 BIBLIOGRAPHY

    Dijkstra, “A Note on Two Problems in Connexion with Graphs,” Numerische Mathematik, Vol. 1, pp. 269-270, 1959. B. P. Dobrin, T. Viero, and ...

  • 算法分析与设计

    W. Dijkstra: A note on two problems in connexion with graphs. In: Numerische Mathematik. 1 (1959), S. 269–271 ·Thomas H. Cormen, Charles E. ...

  • 课件-城市网络模型与算法03

    W.(1959). A Note on Two Problems in Connexion with Graphs. , , Numer. Math., 1:269-271, 1959. Gallo G. and Pallottino S.(1988). Shortest ...

  • Duration 36 months

    W. Dijkstra; A note on two problems in connexion with graphs; Numerische Mathematik ; 1:269; 1959 [6] E. Gamma, R. Helm, R. Johnson, J. ...

  • 移动设备的地理信息系统软件平台

    4. E.W. Dijkstra, A Note on Two Problems in Connexion with Graphs, Numerische Mathematik, 1, 269-271, 1959. 关于作者 罗景山是一名澳门大学科技学院...

站点地图 | 文档上传 | 侵权投诉 | 手机版
本站所有资源均来自互联网,本站只负责收集和整理,均不承担任何法律责任,如有侵权等其它行为请联系我们.
文档下载 Copyright 2013 doc.guandang.net All Rights Reserved.  -  email