Dijkstra's algorithm running time with Array

Question

in wikipedia they state under the Heading: "running time" for Dijstras algorithm is

O(|V|^2 + |E|*decreaseKey) = O(|V|)

Dijkstra's_algorithm

This is my first time analyzing time complexity for an algoritm, but in my opinion it should be:

Outerloop (while Q is not empty) will take O(|v|) time
Findmin in an array should take O(|v| )
Once Min is found then examine all neighbors which can take O(|E|)
then updating they keys for these neigbors is done in constant time C

so we will have

O(V)*( O(|V|) + O(|E|)C ) = O(|V|^2 + O(|V||E|* C) ) = O(|V|^2)

my question is about the term:

O(|V|*|E|*C)

In Wikipedia they don't even bother the |V| factor at all why? is my analysis wrong?

I'm not sure what you mean by "bothering the |V| factor", but |V|*|E| is inaccurate. Each edge is only visited at most twice (when each of its endpoints are visited), so 2*|E| is more accurate, which is just O(|E|). |E| in a simple graph is at most the number of vertices in the complete graph of |V| vertices, which is (|V|^2 - |V|)/2 = O(|V|^2). — Paul
– Paul, Commented Feb 9, 2017 at 9:14

Ry- · Accepted Answer · 2017-02-09 09:10:28Z

2

The issue in your logic is here:

Once Min is found then examine all neighbors which can take O(|E|)

A single node can only have O(|V|) neighbours, not O(|E|). E is all the edges in the graph.

answered Feb 9, 2017 at 9:10

Ry-♦

226k56 gold badges496 silver badges504 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

J.doe Over a year ago

ok but how do they come to this formula: "for any implementation for the vertex set the running time is in" O(|E|*T_{dk} + |V|*T_{em} ) where em = extract minimum and dk = decrease key. I get the fact that T_{em} is O(|V|) (when using array ), but why and where does the |E| come from? @Ryan

Collectives™ on Stack Overflow

Dijkstra's algorithm running time with Array

1 Answer 1

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related