Online citations, reference lists, and bibliographies.
← Back to Search

A Note On Two Problems In Connexion With Graphs

E. Dijkstra
Published 1959 · Mathematics, Computer Science

Save to my Library
Download PDF
Analyze on Scholarcy
Share
We consider n points (nodes), some or all pairs of which are connected by a branch; the length of each branch is given. We restrict ourselves to the case where at least one path 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 ; III. the remaining branches (rejected or not yet considered). The nodes are subdivided into two sets: A. the nodes connected by the branches of set I, B. the remaining nodes (one and only one branch of set II will lead to each of these nodes), We start the construction by choosing an arbitrary node as the only member of set A, and by placing all branches that end in this node in set II. To start with, set I is empty. From then onwards we perform the following two steps repeatedly. Step 1. The shortest branch of set II is removed from this set and added to
This paper references



This paper is referenced by
10.1109/TNSM.2018.2876845
RDNA: Residue-Defined Networking Architecture Enabling Ultra-Reliable Low-Latency Datacenters
Alextian B. Liberato (2018)
10.1109/CNNA.1994.381671
Analog combinatorics and cellular automata-key algorithms and layout design
P. Venetianer (1994)
10.1007/s00778-017-0464-7
I/O-efficient algorithms for top-k nearest keyword search in massive graphs
Qiankun Zhu (2017)
10.5220/0006480604220427
Computing Path Bundles in Bipartite Networks
V. Parque (2017)
10.1109/ITSC.2018.8569627
A Prioritized Routing Assistant for Flow of Traffic
G. Gupta (2018)
10.5539/MAS.V12N6P44
Saving Travel Time as an Urban Planning Instrument. Case Study: Manizales, Colombia
Carlos A. Moncada (2018)
10.1109/ICC.2009.5198771
Availability Evaluation of Hybrid Wireless Optical Broadband Access Networks
Moritz Kiese (2009)
10.1109/ONDM.2012.6210195
Suboptimal PON network designing algorithm for minimizing deployment cost of optical fiber cables
A. Agata (2012)
10.1016/j.jag.2010.07.003
Path-finding through flexible hierarchical road networks: An experiential approach using taxi trajectory data
Q. Li (2011)
10.1016/J.SBSPRO.2011.08.016
Integration of Information and Optimization Models for Vehicle Routing in Urban Areas
J. Ehmke (2011)
10.1016/j.ress.2017.10.026
Stochastic shortest path network interdiction with a case study of Arizona-Mexico border
J. Zhang (2018)
10.1109/TITS.2019.2944134
Car4Pac: Last Mile Parcel Delivery Through Intelligent Car Trip Sharing
Fangxin Wang (2020)
10.1016/J.PETROL.2016.11.011
Fast marching method assisted sector modeling: Application to simulation of giant reservoir models
Behzad Pouladi (2017)
Routing of Electric Vehicles in a Stochastic Network with Non-recurrent Incidents
M. Arani (2020)
10.1109/NoCS.2013.6558405
GCA: Global congestion awareness for load balance in Networks-on-Chip
M. Ramakrishna (2013)
10.3389/neuro.07.019.2009
Scale-Invariant Transition Probabilities in Free Word Association Trajectories
M. Costa (2009)
10.1007/BF01580382
Shortest path algorithms for knapsack type problems
A. Frieze (1976)
10.1145/362280.362308
Remark on algorithm 420 [J6]
I. Macleod (1973)
10.1007/BF01957167
Devisenarbitrage als Flußprobleme
R. Horst (1975)
10.1111/J.1435-5597.1974.TB00931.X
Hierarchical location analysis for integrated area planning in rural India
S. Banerji (1974)
Nuclear Reactor Refueling Optimization
D. Bell (1974)
Form Dynamic Programming To Search Algorithms With Functional Costs
A. Martelli (1975)
Issues and Strategies Involved in Developing Agent-Based Multimodal Network Simulation Model for Transportation Planning: Lessons from a Case Study on the Troronto and Hamilton Area
A. Weiss (2013)
10.1287/trsc.22.1.1
Survey Paper - Time Window Constrained Routing and Scheduling Problems
M. Solomon (1988)
Fixed-point semantics and the representation of algorithms on large data
M. Rougemont (1988)
10.1109/DCS.1988.12534
A new node-join-tree distributed algorithm for minimum weight spanning trees
Y. Lien (1988)
10.1029/WR022I008P01197
A Heuristic Solution Procedure for Expansion Sequencing Problems
S. K. Kim (1986)
10.1109/TC.1982.1676107
A Distributed Algorithm for Shortest Paths
Chen (1982)
10.1007/978-3-642-69546-9_134
Terminplanung für Wartungs-Grossereignisse an Flugzeugen und deren Optimierung Hinsichtlich Nutzung der Wartungsabstände
Sotirios Kougioumtzoglou (1984)
10.1016/0307-904X(83)90158-0
An algorithm to evaluate public transportation stops for minimizing passenger walking distance
Avashai Ceder (1983)
10.1051/RO/1983170403571
Plus court chemin avec contraintes d'horaires
J. Desrosiers (1983)
10.1109/CDC.1982.268162
Optimal control of water distribution systems by network flow theory
S. Miyaoka (1982)
See more
Semantic Scholar Logo Some data provided by SemanticScholar