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

@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