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;
}

Sieve of Eratosthenes used to determine prime numbers. A bool array in taken and initialized to false
first of all it starts with 2 and updates index of bool array of all multiples of 2 to be true..

like 4,6,8..but not 2 which is kept false. next false number is picked which is 3..and all its multiples are updated true like 6,9,12,15...updated true but 3 is kept false

similarly it is followed..

all numbers in the end which are false are primes.

then next false number is picked

int main() { static bool b[100000];

for(int i=2;i<=30000;i+=1)

{

if(!b[i])

{for(int j=2;j*i<30000;j++)

{

    b[i*j]=true;

}

}

} for(int i=2;i<30000;i++)

{

if(!b[i])

{

printf("%d",i);

}

}

return 0;

}