0
$\begingroup$

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|)$?

$\endgroup$
  • $\begingroup$ Did you miss the part where it can be optimized to O(|E| |V|log|V|) using a fibonacci heap?, So how do you suggest optimizing away the log|V| part? $\endgroup$ – Johan - reinstate Monica May 8 '16 at 20:42
2
$\begingroup$

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|)$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.