I want it in O(n logn) using STL in c++ .
#include
#include
#include
#include
// limit of unsigned int
#define INFINITY 65535
struct nodeDistance
{
int node;
unsigned int distance;
};
// This is the basis on which the elements of a priority queue are sorted and
// kept in the queue, here the criteria is that the node with smaller distance should
// come above the one with larger distance
class CompareDist
{
public:
bool operator()(nodeDistance& n1, nodeDistance& n2)
{
if (n1.distance > n2.distance)
return true;
else
return false;
}
};
// This implementation take
// s --> source node (represented by an index)
// size --> the total number of nodes in the graph
// graph --> pointer to a 2D array graph[size][size] that contains information about all the edges in the graph
// Instead of a 2D array you can also use an adjacency list if the graph is sparse
void dijkstra(int s, int size, unsigned int **graph)
{
int mini;
bool *visited = new bool [size];
unsigned int *dist = new unsigned int [size];
// initialize the dist of each node as infinity and visited status as false
for (int i = 0; i < size; i)
{
dist[i] = INFINITY;
visited[i] = false;
}
// the distance of the source to itself is 0
dist[s] = 0;
// instantiate a priority queue with the structure and comparison criteria
// as defined above
priority_queue< nodeDistance, vector< nodeDistance >, CompareDist> pq;
// Create the first node as the source and put it into the queue
nodeDistance first = {s,0};
pq.push(first);
// While queue is not empty, pick the topmost node
// using it's neighbors update the distance of each node that can be reached
// and insert that node in the priority queue
while(!pq.empty())
{
nodeDistance temp = pq.top();
pq.pop();
int node= temp.node;
for(int i=0;i < size;i )
{
if(graph[node][i]!=0)
{
// Update the distance if it is smaller than the current distance
if(dist[i] > (dist[node] graph[node][i]))
dist[i] = dist[node] graph[node][i];
// If not visited put it into the queue
if(!visited[i])
{
nodeDistance newNode;
newNode.node=i;
newNode.distance=dist[i];
pq.push(newNode);
visited[i]=true;
}
}
}
}
cout << "The shortest distance from " << s << " to all the nodes is" << endl;
for(int i=0;i < size;i )
{
cout << i << " : " << dist[i] << endl;
}
cout << endl << endl;
}
Source: http://learn.hackerearth.com/tutorial/graph-algorithms/10/dijkstras-algorithm/
2 Likes
This is my all time favorite video of Dijkstra Algorithm. Try it and your concept will be crystal clear 
: Dijkstra Algorithm
This is my implementation for EZDIJKST. Hope it helps. Link for code on ideone is here.
It is implemented without class using set container of STL.
#include<bits/stdc++.h>
using namespace std;
struct node
{
int data;
node *next;
int wt;
};
struct pro
{
int n;
int dis;
};
node *push(node *head,int a,int wt)
{
node *t=new node;
t->data=a;
t->wt=wt;
t->next=NULL;
if(head==NULL)
{
head=t;
return head;
}
node *p=head;
while(p->data!=a && p->next!=NULL)
{
p=p->next;
}
if(p->data==a)
{
if(p->wt<wt)
{
return head;
}
else
{
p->wt=wt;
return head;
}
}
p->next=t;
return head;
}
class compare
{
public:
bool operator()(pro &n1,pro &n2)
{
if(n1.dis>n2.dis)
{
return true;
}
else
{
return false;
}
}
};
class graph
{
int v;
node *head;
public:
graph(int V)
{
v=V;
head=new node[v];
for(int i=0;i<v;i++)
{
head[i]=NULL;
}
}
void add(int a,int b,int wt)
{
head[a]=push(head[a],b,wt);
head[b]=push(head[b],a,wt);
}
void Dijkstra(int srt);
void f()
{
for(int i=0;i<v;i++)
{
delete head[i];
}
delete head;
}
void display()
{
/*for(int i=0;i<v;i++)
{
node w=head[i];
while(w!=NULL)
{
cout<wt<<" “;
w=w->next;
}
cout<<”\n";
}/
node *w=head[0];
while(w!=NULL)
{
cout<data<<" “<wt<<”\n";
w=w->next;
}
}
};
void graph::Dijkstra(int srt)
{
int dis[v];
int vis[v];
for(int i=0;i<v;i++)
{
dis[i]=INT_MAX;
vis[i]=false;
}
priority_queue<pro,vector,compare> p;
pro f={srt,0};
p.push(f);
dis[srt]=0;
vis[srt]=true;
while(!p.empty())
{
pro r=p.top();
p.pop();
int k=r.n;
//cout<<k<<“\n”;
node *w=head[k];
while(w!=NULL)
{
int y=w->data;
if(dis[k]!=INT_MAX && dis[y]>dis[k]+w->wt)
{
dis[y]=dis[k]+w->wt;
}
if(!vis[y])
{
pro g;
g.n=y;
g.dis=dis[y];
p.push(g);
vis[y]=true;
}
w=w->next;
}
}
for(int i=0;i<v;i++)
{
if(i!=srt)
{
if(dis[i]==INT_MAX)
{
cout<<"-1"<<" ";
}
else
{
cout<<dis[i]<<" ";
}
}
}
cout<<"\n";
}
int main()
{
int tc;
cin>>tc;
while(tc–)
{
int n,m;
cin>>n>>m;
graph g(n);
int i;
for(i=0;i<m;i++)
{
int a,b,wt;
cin>>a>>b>>wt;
g.add(a-1,b-1,wt);
}
int s;
cin>>s;
g.Dijkstra(s-1);
//g.display();
}
}
Here is an implementation which I use which uses adjacency list and min heaps. This link helped a lot:
Code:
1 Like
#include <bits/stdc++.h>
using namespace std;
#define MAX 100001
#define INF (1<<20)
#define pii pair< int, int >
#define pb(x) push_back(x)
struct comp {
bool operator() (const pii &a, const pii &b) {
return a.second > b.second;
}
};
priority_queue< pii, vector< pii >, comp > Q; //priority_queue (min)
vector< pii > G[MAX];
int D[MAX];
bool F[MAX];
int main() {
int i, u, v, w, sz, nodes, edges, starting;
// create graph
scanf("%d %d", &nodes, &edges);
for(i=0; i<edges; i++) {
scanf("%d %d %d", &u, &v, &w);
G[u].pb(pii(v, w));
// G[v].pb(pii(u, w)); // for undirected
}
scanf("%d", &starting); //starting node
// initialize distance vector
for(i=1; i<=nodes; i++) D[i] = INF;
D[starting] = 0;
Q.push(pii(starting, 0));
// dijkstra
while(!Q.empty()) {
u = Q.top().first;
Q.pop();
if(F[u]) continue;
sz = G[u].size();
for(i=0; i<sz; i++) {
v = G[u][i].first; //stores the node
w = G[u][i].second; //stores the weight
if(!F[v] && D[u]+w < D[v]) //not visited along smaller distance
{
D[v] = D[u] + w;
Q.push(pii(v, D[v]));
}
}
F[u] = 1; // done with u
}
for(i=1; i<=nodes; i++) printf("Node %d, min weight = %d\n", i, D[i]);
return 0;
}
Here is the Fast Dijsktra implementation from the Stanford ACM Notebook 
// Implementation of Dijkstra's algorithm using adjacency lists
// and priority queue for efficiency.
//
// Running time: O(|E| log |V|)
#include <queue>
#include <cstdio>
using namespace std;
const int INF = 2000000000;
typedef pair<int, int> PII;
int main() {
int N, s, t;
scanf("%d%d%d", &N, &s, &t);
vector<vector<PII> > edges(N);
for (int i = 0; i < N; i++) {
int M;
scanf("%d", &M);
for (int j = 0; j < M; j++) {
int vertex, dist;
scanf("%d%d", &vertex, &dist);
edges[i].push_back(make_pair(dist, vertex)); // note order of arguments here
}
}
// use priority queue in which top element has the "smallest" priority
priority_queue<PII, vector<PII>, greater<PII> > Q;
vector<int> dist(N, INF), dad(N, -1);
Q.push(make_pair(0, s));
dist[s] = 0;
while (!Q.empty()) {
PII p = Q.top();
Q.pop();
int here = p.second;
if (here == t) break;
if (dist[here] != p.first) continue;
for (vector<PII>::iterator it = edges[here].begin(); it != edges[here].end(); it++) {
if (dist[here] + it->first < dist[it->second]) {
dist[it->second] = dist[here] + it->first;
dad[it->second] = here;
Q.push(make_pair(dist[it->second], it->second));
}
}
}
printf("%d\n", dist[t]);
if (dist[t] < INF)
for (int i = t; i != -1; i = dad[i])
printf("%d%c", i, (i == s ? '\n' : ' '));
return 0;
}use vector< list< pair< int,int > > >adj(n+1); to create adjacency list and storing cost of edge as first element of the pair.Thereafter,use set from STL (or priority queue) as it reduces the complexity of the code.Use:
set< pair< int,int > > pq;
why we dont need to have a boolean visited array while implementing with adjacency list ??
Your implementation is wrong . You are marking a vertex as “visited” as soon it is pushed into priority queue . This makes is “non visitable” in cases it is realxed by by some other vertex .