In a multi-stage graph algorithm for shortest path, we minimize cost for every edge exactly once. So the Time Complexity is $O(E)$. However, in the worst case, we get a complete graph, which has edges $E = n*(n-1)/2$, so worst time complexity then becomes $O(E) = O(n^2).$
Note that in this case too, every edge is processed exactly once.