title: Complexity Of Dijkstra's algorithm
body: <p>I read from many sources that Dijkstra's Shortest Path also will run in O(V^2) complexity if using a naive way to get the min element (linear search). However, it can be optimised to O(VLogV) if priority queue is used as this data structure will return min element in O(1) time but takes O(LogV) time to restore the heap property after deleting the min element.</p>
  
  <p>I have implemented Dijkstra's algo in the following code for the UVA problem at this link: <a href="https://uva.onlinejudge.org/index.php?option=com_onlinejudge&amp;Itemid=8&amp;category=16&amp;page=show_problem&amp;problem=1927" rel="noreferrer">https://uva.onlinejudge.org/index.php?option=com_onlinejudge&amp;Itemid=8&amp;category=16&amp;page=show_problem&amp;problem=1927</a>:</p>
  
  <pre><code>#include&lt;iostream&gt;
  #include&lt;vector&gt;
  #include &lt;climits&gt;
  #include &lt;cmath&gt;
  #include &lt;set&gt;
  
  using namespace std;
  
  #define rep(a,b,c) for(int c=a;c&lt;b;c++)
  
  typedef std::vector&lt;int&gt; VI;
  typedef std::vector&lt;VI&gt; VVI;
  
  struct cmp {
      bool operator()(const pair&lt;int,int&gt; &amp;a,const pair&lt;int,int&gt; &amp;b) const {
          return a.second &lt; b.second;
      }
  };
  
  void sp(VVI &amp;graph,set&lt;pair&lt;int,int&gt;,cmp&gt; &amp;minv,VI &amp;ans,int S,int T) {
      int e = -1;
      minv.insert(pair&lt;int,int&gt;(S,0));
      rep(0,graph.size() &amp;&amp; !minv.empty() &amp;&amp; minv.begin()-&gt;first != T,s) {
          e = minv.begin()-&gt;first;
          minv.erase(minv.begin());
          int nb = 0;
          rep(0,graph[e].size(),d) {
              nb = d;
              if(graph[e][d] != INT_MAX &amp;&amp; ans[e] + graph[e][d] &lt; ans[d]) {
                  set&lt;pair&lt;int,int&gt;,cmp&gt;::iterator si = minv.find(pair&lt;int,int&gt;(d,ans[d]));
                  if(si != minv.end())
                      minv.erase(*si);
                  ans[d] = ans[e] + graph[e][d];
                  minv.insert(pair&lt;int,int&gt;(d,ans[d]));
              }
          }
      }
  }
  
  int main(void) {
      int cc = 0,N = 0,M = 0,S = -1,T = -1,A=-1,B=-1,W=-1;
      VVI graph;
      VI ans;
      set&lt;pair&lt;int,int&gt;,cmp&gt; minv;
      cin &gt;&gt; cc;
  
      rep(0,cc,i) {
          cin &gt;&gt; N &gt;&gt; M &gt;&gt; S &gt;&gt; T;
          graph.clear();
          ans.clear();
          graph.assign(N,VI());
          ans.assign(graph.size(),INT_MAX);
          minv.clear();
          rep(0,N,j) {
              graph[j].assign(N,INT_MAX);
          }
          ans[S] = 0;
          graph[S][S] = 0;
          rep(0,M,j) {
              cin &gt;&gt; A &gt;&gt; B &gt;&gt; W;
              graph[A][B] = min(W,graph[A][B]);
              graph[B][A] = min(W,graph[B][A]);
          }
          sp(graph,minv,ans,S,T);
          cout &lt;&lt; "Case #" &lt;&lt; i + 1 &lt;&lt; ": ";
          if(ans[T] != INT_MAX)
              cout &lt;&lt; ans[T] &lt;&lt; endl;
          else
              cout &lt;&lt; "unreachable" &lt;&lt; endl;
      }
  }
  </code></pre>
  
  <p>Based on my analysis, my algorithm has a O(VLogV) complexity. The STL std::set is implemented as a binary search tree. Furthermore, the set is sorted too.
  Hence getting the minimum element from it is O(1), insertion and deletion is O(LogV) each. However, I am still getting a TLE from this problem which should be solvable in O(VLogV) based on the given time limit.</p>
  
  <p>This led me to think deeper. What if all nodes were interconnected such that each vertex V has V-1 neighbours? Won't it make Dijkstra's algorithm run in O(V^2) since each vertex has to look at V-1,V-2,V-3... nodes every round?</p>
  
  <p>On second thoughts, I might have misinterpreted the worst case complexity. Could someone please advise me on the following issues:</p>
  
  <ol>
  <li>How is Dijkstra's algo O(VLogV) especially given the above counterexample?</li>
  <li>How could I optimise my code so that it could achieve O(VLogV) complexity (or better)?</li>
  </ol>
  
  <p>Edit:</p>
  
  <p>I realised that my program does not run in O(ElogV) after all. The bottleneck is caused by my input processing which runs in O(V^2). The dijkstra part indeed runs in (ElogV).</p>