[Solved]: Complexity of the Dijkstra algorithm

Problem Detail: 

I'm little confused by computing a time complexity for Dijkstra algorithm. It is said that the complexity is in $O(|V|^2)$ - Wikipedia - Dijkstra, which I understand. It's because for each node, we could theoretically relax edges going to each vertex so it is $n * n$ times, respectively $n(n-1)$.

On the other hand, I can't figure out why this complexity isn't $O(|E|+|V|)$. For each $v \in V$, we relax only those edges $e$, which weren't computed yet. If vertex $v$ is already computed (red on gif above), we don't need to work with it anymore.

So can I say that in one way, it is true that Dijkstra is in $O(|V|)$, but if we can put into the computation number of edges, I can say that it is in $O(|V|+|E|)$?

Asked By : Milano Slesarik

Answered By : emab

For each v from V, we relax only those edges e, which werent computed yet. If vertex v is already computed (red on gif above), we don't need to work with it anymore.

Your are assuming that each edge is visited only once, but this assumption is not quite right. Let's say we have two sets $S$ and $S'$, such that $V=S \cup S'$ and $S$ is the set of vertices, for which we have found the shortest path from source $s$. Each time, we need to find an edge $e=(u,v)$ ($u \in S$ and $v \in S'$) that sits on a shortest path, but how do you find this edge? You need to either

(1) use a brute-force algorithm and spend $O(|V|)$ to look at all edges $e=(u,v)$ ($u \in S$ and $v \in S'$) for finding the minimum one, which takes $O(|V|^2)$ (because each time you are looking at the same edge that are not in the shortest path).

or

(2) use a min-heap and spend $O( \log |V| ) $ for finding that edge, and achieve $O( (|V| + |E|)\cdot \log |V| )$ overall running time.

However, if the graph is unweighted, your assumption is right and you can achieve the running time $O(|V|+|E|)$.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/57226