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

//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 ...
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),...
(1959). A note on two problems in connexion with graphs. Numerische Mathematik 1, 269–271. ? 原理: Bellman最优化原理 若P是网络G中从Vs到Vt 的一条...
W. Dijkstra: A note on two problems in connexion with graphs. In: Numerische Mathematik. 1 (1959), S. 269–271 Thomas H. Cormen, Charles E. ...
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. ...
W.(1959). A Note on Two Problems in Connexion with Graphs. , , Numer. Math., 1:269-271, 1959. Gallo G. and Pallottino S.(1988). Shortest ...
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. 关于作者 罗景山是一名澳门大学科技学院...
热门文档