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
