DocumentCode
1347606
Title
A note on the complexity of Dijkstra´s algorithm for graphs with weighted vertices
Author
Barbehenn, Michael
Author_Institution
Motorola GmbH, Munchen, Germany
Volume
47
Issue
2
fYear
1998
fDate
2/1/1998 12:00:00 AM
Firstpage
263
Abstract
Let G(V, E) be a directed graph in which each vertex has a nonnegative weight. The cost of a path between two vertices in G is the sum of the weights of the vertices on that path. We show that, for such graphs, the time complexity of Dijkstra´s algorithm (E.W. Dijkstra, 1959), implemented with a binary heap, is O(|E|+|V|log|V|)
Keywords
computational complexity; directed graphs; Dijkstra algorithm; binary heap; directed graph; nonnegative weight; time complexity; weighted vertices; Cost function; Data structures; Orbital robotics; Space exploration; Testing;
fLanguage
English
Journal_Title
Computers, IEEE Transactions on
Publisher
ieee
ISSN
0018-9340
Type
jour
DOI
10.1109/12.663776
Filename
663776
Link To Document