Vidal's library
Title: A note on two problems in connexion with graphs
Author: Edsger W. Dijkstra
Journal: Numerische Mathematik
Volume: 1
Pages: 269--271
Year: 1959
Abstract: We consider a graph with n vertices, all pairs of which are connected by an edge; each edge is of given positive length. The following two basic problems are solved. Problem 1: construct the tree of minimal total length between the n vertices. (A tree is a graph with one and only one path between any two vertices.) Problem 2: find the path of minimal total length between two given vertices.

Cited by 1403  -  Google Scholar

@Article{dijkstra59a,
  author =	 {Edsger W. Dijkstra},
  title =	 {A note on two problems in connexion with graphs},
  journal =	 {Numerische Mathematik},
  year =	 1959,
  volume =	 1,
  pages =	 {269--271},
  abstract =	 {We consider a graph with n vertices, all pairs of
                  which are connected by an edge; each edge is of
                  given positive length. The following two basic
                  problems are solved. Problem 1: construct the tree
                  of minimal total length between the n vertices. (A
                  tree is a graph with one and only one path between
                  any two vertices.) Problem 2: find the path of
                  minimal total length between two given vertices.},
  url = 	 {http://jmvidal.cse.sc.edu/library/dijkstra59a.pdf},
  cluster = 	 {531581949522259482},
  keywords = 	 {distributed algorithms}
}
Last modified: Wed Mar 9 10:13:15 EST 2011