Блог пользователя ap_hawkdown

Автор ap_hawkdown, 10 лет назад, По-английски

Simple Dijkstra in C++

Pseudo Code From CLRS:

Dijkstra(G,w,s)

1 -Initialise single source(G,s)

2 -S='\0'

3 -Q=G.V

4 -while Q!='\0'

5 --u=Extract-MIN(Q)

6 --S=S U {u}

7 --for each vertex v belongs to G.Adj[u]

8 ----RELAX(u,v,w)

Function Relax is described in below C++ code

This Blog entry is with reference to problem http://www.spoj.com/problems/EZDIJKST/

/*This is the simplest implemententation of Dijkstra Algorithm in C++. Graph is implemented via STL container list using an adjacency list representation This includes use of STL container Set as a pririty queue thus doing away the need of implementing heaps like in C. */

Code Below:


LL d[1000000];//Distance function list<pair<int,int> > *graph; void dijkstra(int root) { set<pair<int,int> > pq; /* A set helps insertion and extraction operations in logarithmic time. This set maintains (distance,vertex number) pair sorted on basis of distance*/ set<pair<int,int> > ::iterator it; int u,v,wt; list<pair<int,int> > :: iterator i; d[root]=0; pq.insert(pair<int,int>(0,root)); while(pq.size()!=0) { it=pq.begin(); u=it->second; pq.erase(it); for(i=graph[u].begin(); i!=graph[u].end(); i++) { v=i->first; wt=i->second; //Relax u-v edge with weight wt below: if(d[v]>d[u]+wt) { if(d[v]!=1e8) { pq.erase(pq.find(pair<int,int>(d[v],v))); } d[v]=d[u]+wt; pq.insert(pair<int,int>(d[v],v)); } //Relax ends } } } void addedge(int src,int des,int wt) { pair<int,int> x; x.first=des; x.second=wt; graph[src].push_front(x); //here we are consering directed graph so. /* include in case of undirected graph x.first=src; x.second=wt; graph[des].push_front(x); */ //This algorithm works in same way for undirected graph } int main() { int i; int t; cin>>t; while(t--){ int v,e,src,des,wt; cin>>v>>e; //Initialise all d[v] to a large number for(i=0; i<=v; i++) { d[i]=1e8; /*Do not use INF because mathematical operations performed on it will cause overflow in some cases you may need higher values like 1e18 etc. as per constraints */ } graph=new list<pair<int,int> >[v+1]; for(i=0; i<e; i++) { cin>>src>>des>>wt; addedge(src,des,wt); } int x,y; cin>>x>>y; dijkstra(x); if(d[y]!=1e8) cout<<d[y]<<endl; else cout<<"NO"<<endl; } return 0; }
  • Проголосовать: нравится
  • -25
  • Проголосовать: не нравится

»
10 лет назад, # |
  Проголосовать: нравится +9 Проголосовать: не нравится

Suggestions are appreciated. Downvotes are easy to do.

  • »
    »
    10 лет назад, # ^ |
      Проголосовать: нравится +9 Проголосовать: не нравится

    Not sure why you have so many downvotes, it might be because your code is just copy-pasted, there was some way to post code correctly but I don't remember how it was done.

    About the Djikstra, I'd recommend priority_queue instead of set, it's main purpose is to extract the largest/smallest element and it's much lighter than set. Set is usually heavy and even though they are both logarithmic I've had instances where set/map work really slow compared to other logarithmic structures.

    • »
      »
      »
      10 лет назад, # ^ |
        Проголосовать: нравится +8 Проголосовать: не нравится

      ~~~~~            
      Your code here...
      ~~~~~            

  • »
    »
    10 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Shouldn't the "set" be a "multiset" as there can be many occurrences of a distance x and set only keeps one instance of them, just wondering ?

»
10 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

Thanks Guys.

Now my code looks more presentable.

@Enchom

Actually i am not quite familiar with priority_queue so i did not use it.Thanks for your help.

  • »
    »
    10 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Yeah, I see.

    Priority queue is very simple structure implemented using heap. It is easily implemented, and I used to code it myself for years since I wasn't familiar with STL. It supports adding elements, getting the top element and removing the top element, while the top is always the largest one. For Djikstra's algorithm we want the smallest one, not the largest, so you can either create your own comparators or simply add -val instead of val when adding elements to the queue.

    Of course, you can always use set, it's a common structure, but as I said, it's heavier :)

»
10 лет назад, # |
Rev. 5   Проголосовать: нравится 0 Проголосовать: не нравится

@ap_hawkdown- I know that if(d[v]!=1e8) { pq.erase(pq.find(pair<int,int>(d[v],v))); } this lines are necessary for Dijktra's algo. But I tried without this and my code was accepted on spoj???? Why is it so?

here is my code https://ideone.com/9JiIMw

  • »
    »
    10 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    As Far as i realized this line is not necessary because even if you don't delete the old edge weights,the new edge weights will still be minimum hence the minimum weight will be chosen and the old weights will be present without causing harm.

    For instance if an old egde(which was meant to be deleted) is encountered then it will be disregarded because of this statement

    " if(d[v]>d[u]+wt) "

    which it does not satisfy hence it wont cause any bug in code :) :)