How to implement Dijkstra Algorithmin c++?

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 :slight_smile:
: 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:
https://www.quora.com/What-is-the-most-simple-efficient-C++-code-for-Dijkstras-shortest-path-algorithm

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

This is how I implement Djikstra’s algo in C++ using priority queues :slight_smile:

http://ideone.com/aAStOw

Here is the Fast Dijsktra implementation from the Stanford ACM Notebook :slight_smile:

// 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 ??