Complexity of Dijkstra shortest path

Question

I don't seem to understand Wikipedia's paragraph on why Dijkstra shortest path problem is O((|E|+|V|)*log(|V|))

Supposing that I used a binary heap, extracting all vertices would require V*logV, where does the E*logV term come from?

Can somebody enlighten me please?

Answer 1

When you extract a vertex from the heap, you then need to examine all the edges coming out of that node and do some processing for each neighbour (decreasing key).

This means that we end up examining all edges during the entire algorithm, and may require O(logV) for each edge, so total of O(ElogV) in addition to the O(VlogV) cost for removing the minimum entry from the heap for each vertex.

Answer 2

In Dijstra algorithm basically you add all the vertices that are available to u as an option and you take the minimum of them. Basically if you go step by step.

Node : only the source : Edges : Direct edges coming out of the source.

Adding each edge would take log(Edge_taken_in) time Take the minimum of them all and remove that one.

Add all the edges coming out of the node you just discovered add the cost of reaching that node and add them all to our heap or any O(log(n)) working Data Structure and repeat.

Ok now these steps will keep on going till each of the vertices are discovered.

1. For each of the Vertices you will add all the edges going out of it (maximum value of this could be O(V) (if the node is connected to all the other nodes)).

2. Remove one that is the minimum and remake the heap/(and DS u using).

OK so we get Two things to take care of.

First one O(V) insertions V times give

O((V^2)log(V))

(U may say V^2(log(E))

but that will be the same as

log (E) = log(V^2) = O(log(V))).

Now the second step will go for V times as for each node you get by extracting the edge with the minimum cost.

Hence

T = O( (V^2)log(V) + (V)O(log(V)))

Now as E=O(V^2) Sp we may say.

T=O((E+V) log(V)).

Here is the code

#include<iostream>
#include<vector>
#include<utility>
#include<limits.h>
#include<queue>
using namespace std;
class compare{
public:
  bool operator()(pair<int ,int> p,pair<int ,int> q)
  {
    if(p.first<q.first)
      return false;
    else
      return true;
  }
};
int main()
{
  int count,min,mini,n,m,i,x,y,d,s;
  cin>>n>>m;
  int a[n];
  bool b[n];
  priority_queue<pair<int ,int>,vector<pair<int , int> >,compare>pq; 
  pair<int ,int>p;
  vector<pair<int ,int > >V[n];
  for(i=0;i<m;++i)
    {
      cin>>x>>y>>d;
      //  x--;y--;
      p.first=y;
      p.second=d;
      V[x].push_back(p);
      p.first=x;
      V[y].push_back(p);
    }
  while(1)
    {
      cout<<"Enter the Source\t";
      cin>>s;
      for(i=0;i<n;++i)
    {
      a[i]=INT_MAX;
      b[i]=false;
    }
      count=1;
      a[s]=0;
      p=make_pair(a[s],s);
      pq.push(p);
      // s--;
      min=0;
      while(!pq.empty() && pq.top().first!=INT_MAX)
    {
      p=pq.top();
      pq.pop();
      cout<<p.first<<" "<<p.second<<endl;
      if(b[p.second]==true)
        {
          continue;
        }
      else
        {
          //in v second is distance and first is index
          mini=p.second;
          for(i=0;i<V[mini].size();++i)
        {
          cout<<i<<" "<<V[mini][i].first<<" "<<a[V[mini][i].first]<<" "<<a[mini]+V[mini][i].second<<endl;
          if(b[V[mini][i].first]==false&&a[V[mini][i].first]>a[mini]+V[mini][i].second)
            {
              a[V[mini][i].first]=a[mini]+V[mini][i].second;
              p=make_pair(a[V[mini][i].first],V[mini][i].first);

              cout<<" *"<<p.first<<" "<<p.second<<endl;
              pq.push(p);
            }
        }
          b[mini]=true;
        }
      cout<<endl<<endl;
    }

      for(i=0;i<n;++i)
    cout<<a[i]<<" ";
      cout<<endl;


    }
  return 0;
}