A note on the complexity of Dijkstra's algorithm for graphs with weighted vertices

被引：192

作者：

Barbehenn, M ^{[1
]}

机构：

[1] Motorola GmbH, D-81829 Munich, Germany

来源：

IEEE TRANSACTIONS ON COMPUTERS | 1998年 / 47卷 / 02期

基金：

美国国家科学基金会;

关键词：

analysis of algorithms; combinatorial problems; data structures;

D O I：

10.1109/12.663776

中图分类号：

TP3 [计算技术、计算机技术];

学科分类号：

0812 ;

摘要：

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. In this paper, we show that, for such graphs, the time complexity of Dijkstra's algorithm, implemented with a binary heap, is O(\E\ + \V\ log \V\).

引用

页码：263 / 263

页数：1

共 4 条

[1] EFFICIENT SEARCH AND HIERARCHICAL MOTION PLANNING BY DYNAMICALLY MAINTAINING SINGLE-SOURCE SHORTEST PATHS TREES [J].