A note on the complexity of Dijkstra's algorithm for graphs with weighted vertices
M. Barbehenn · IEEE Transactions on Computers · 1998
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|).