Diplomate's blog

By Diplomate, history, 14 months ago, In English,

What is the best for Dijkstra's algorithm: set with erasing of the vertices adjacent to the current one and the subsequent insertion of them with the new values or a priority_queue with a lot of irrelevant vertices? Or maybe some other approach using std?

 
 
 
 
  • Vote: I like it  
  • +11
  • Vote: I do not like it  

»
14 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I remember in an article on Topcoder about STL (you can google it easily, part 2), they are said to not differ much in terms of performance, only by 0.1% in practice.

Dijkstra with set, in my opinion, is clearer to code.

  • »
    »
    14 months ago, # ^ |
    Rev. 2   Vote: I like it +13 Vote: I do not like it

    How did you measure that?

    Try solving this with std::set.

    I didn't manage to succeed even though I'm pretty sure my code is optimal enough, std::set is slower than std::priority_queue by more that 30 times on this specific task.

    Submissions' summary

    I have also submitted 20C - Dijkstra? more than 30 times with using many different data structures, so I guess that priority_queue is WAY faster than std::set, at least like 2-3 times, but sometimes this advantage can be up to 20-30 times on some specific graphs.

    The only drawback I've seen so far is that the memory consumed by this Dijkstra is not O(N) but is O(M).

    • »
      »
      »
      14 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      The task from main (sums) could be solved without Dijkstra, in a linear way. You're always adding edges as a kind of a cycle. For this specific problem, set might be slower but I've heard that it's better in general.

      • »
        »
        »
        »
        14 months ago, # ^ |
        Rev. 6   Vote: I like it +10 Vote: I do not like it

        This might be because when priority_queue allocates O(M) memory it will work in . It might be slower for graphs where M is several orders greater than N.

        Why do I think it shouldn't affect really much

        Usually in tasks you see something like 1 ≤ N, M ≤ 105 so, I believe, in general it is better to use priority_queue.

        • »
          »
          »
          »
          »
          14 months ago, # ^ |
          Rev. 3   Vote: I like it +3 Vote: I do not like it

          You are mixing apples and oranges.

          First of all, if you use Dijkstra to solve Sums from MAIN, you should use an O(n^2) implementation, because it is a dense graph. The set/priority_queue implementations are both O(n^2 log n) for dense graphs. The log n overhead is unnecessary.

          Benchmarking set vs. priority queue on dense graphs is pointless, as you shouldn't use either data structure in that setting.

          Second, you are probably doing something wrong/suboptimal in your Sums implementation. I just submitted an O(n^2 log n) solution using Dijkstra with a set for Sums and got 100 points.

          Finally, regarding the big picture: For sparse graphs I've seen a lot of benchmarks. The exact results of this comparison depended on way too many factors, such as the platform, compiler version, and optimization flags used. Still, the result was always (that I remember) that the runtime of one implementation was within twice the runtime of the other. In terms of programming contests (and also in terms of real life) a factor of two is negligible. I would never use the words "much faster" in this context.

          Feel free to choose the implementation you like better, in the tasks when using either is appropriate.

      • »
        »
        »
        »
        6 weeks ago, # ^ |
          Vote: I like it +7 Vote: I do not like it

        off the topic but i wanted to know how to solve the above problem in linear way. I don't know how to approach the problem. Even a little hint would be very helpful.

    • »
      »
      »
      5 weeks ago, # ^ |
        Vote: I like it -18 Vote: I do not like it

      hey....can you tell me the error in my code for dijkstra? 20C problem... here is my code :

      #include <bits/stdc++.h>
      #define F first
      #define S second
      #define pii pair<ll,ll>
      #define piii pair<ll,pair<ll,ll> >
      #define mp make_pair
      #define pb push_back
      #define ll long long
      #define ull unsigned long long
      using namespace std;
      
      const ll mod=1e9+7;
      vector<pair<ll,ll> > adj[100005];
      ll par[100005];
      ll dist[100005];
      
      void djk()
      {
      	par[1] = 1;
      	dist[1] = 0;
      	priority_queue<pair<ll,ll>, vector<pair<ll,ll> >, greater<pair<ll,ll> > > pq;
      	pq.push(mp(0,1));
      	while(!pq.empty())
      	{
      		//cout<<"bug";
      		pair<ll,ll> p = pq.top();
      		pq.pop();
      		ll u = p.S;
      		for(ll i=0;i<adj[u].size();i++)
      		{
      			ll x = adj[u][i].F;
      			ll wt = adj[u][i].S;
                  if(dist[u] + wt < dist[x])
      			{
      				//cout<<u<<" "<<x<<" "<<endl;
      				dist[x] = dist[u] + wt;
      				par[x] = u;
      				pq.push(mp(dist[x], x));
      			}
      		}
      	}
      }
      
      int main()
      {
      	ll n,m,a,b,c;
      	cin>>n>>m;
      	for(ll i=0;i<m;i++)
      	{
      		cin>>a>>b>>c;
      		adj[a].pb(mp(b,c));
      		adj[b].pb(mp(a,c));
      	}
      	for(ll i=1;i<=n;i++)
      		dist[i]=mod;
      	djk();
      	if(dist[n]==mod)
      	{
      		cout<<-1;
      	}
      	else
      	{
      		ll node = n;
      		stack<ll>s;
      		//for(ll i=1;i<=n;i++) cout<<i<<" "<<par[i]<<endl;
      		while(node!=1)
      		{
      			s.push(node);
      			node = par[node];
      		}
      		s.push(1);
      		while(!s.empty())
      		{
      			cout<<s.top()<<" ";
      			s.pop();
      		}
      	}
      }
      
      
      
      • »
        »
        »
        »
        5 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Update : i found the error.... Mod value is required to be much more here.

»
14 months ago, # |
  Vote: I like it +10 Vote: I do not like it

From my experience, priority_queue is much faster, maybe 2x faster than set.

http://codeforces.com/contest/20/status/C?order=BY_CONSUMED_TIME_ASC

  • »
    »
    14 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    A friend of mine has made such "comparisons" as well. You know what? The results were different :D

  • »
    »
    14 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    This is all really weird.)

»
14 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

I tested Dijkstra's speed on this problem on spoj. ( spoj.com/problems/TSHPATH )

As per the results: Set: 1.51 seconds while Priority Queue: 0.98 seconds.

In my opinion too, priority queue is much faster than set.

»
14 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

Correct me if im wrong but priority queue is basically a heap so we get the min element in O(1) whereas set is a balanced bst so extract min is a O(logn) operation

  • »
    »
    14 months ago, # ^ |
      Vote: I like it +6 Vote: I do not like it

    Yes, you are wrong. In a heap you can find the minimum in O(1), but you then need O(log(heap_size)) anyway if you want to remove (pop) it from the heap. Which, in Dijkstra's algorithm, you do need.