### Dijkstra's Algorithm

Dijkstra's algorithm is a single source shortest path (sssp) algorithm. Like BFS, this famous graph searching algorithm is widely used in programming and problem solving, generally used to determine shortest tour in a weighted graph.

This algorithm is almost similar to standard BFS, but instead of using a Queue data structure, it uses a heap like data structure or a priority queue to maintain the weight order of nodes. Here is the algorithm and pseudo-code. You can also look into __Introduction to Algorithms (by C.L.R.S)__.

Here is a short implementation of this algorithm in C++, I assumed that, all the edge-weights are positive, and the max possible distance is less than 2^{20} which is set as INF macro and the graph supports MAX nodes starting from 1 to MAX-1, these macros needs to be set properly.

#### Input format:

N E // number of nodes and edges

E lines containing an edge (u, v, w) on each line

// edge(u, v, w) means weight of edge u-v is w

// u, v in range 1 to N

S // starting node

#### C++ code:

#include <cstdio>

#include <queue>

#include <vector>

using namespace std;

#define MAX 100001

#define INF (1<<20)

#define DEBUG if(0)

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

vector< pii > G[MAX];

int D[MAX];

bool F[MAX];

int main() {

int i, u, v, w, sz, nodes, edges, starting;

DEBUG freopen("in.txt","r", stdin);

// 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);

// initialize graph

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();

DEBUG printf("visiting from %d:", u);

for(i=0; i<sz; i++) {

v = G[u][i].first;

w = G[u][i].second;

if(!F[v] && D[u]+w < D[v]) {

DEBUG printf(" %d,", v);

D[v] = D[u] + w;

Q.push(pii(v, D[v]));

}

}

DEBUG printf("\n");

F[u] = 1; // done with u

}

// result

for(i=1; i<=nodes; i++) printf("Node %d, min weight = %d\n", i, D[i]);

return 0;

}

This is a straight forward implementation, according to the problem solving purpose, changes are to be made here and there.

One thing. If a node has been push more then one time it will also pop more then one times. Consider the graph;

ReplyDelete6 6

1 2 3

1 4 7

2 3 10

2 4 3

4 5 1

4 6 2

1

Here 4 is pop'ed 2 times. I know its should not cause any problem but is not it unnecessary? If we do like below is there could be any problem?

// dijkstra

while(!Q.empty()) {

u = Q.top().first;

Q.pop();

if(F[u]) continue; //If already done forget it

sz = G[u].size();

No, It will not cause any trouble. You can do that :)

ReplyDeleteCan you please suggest how to modify the code if I want to find the shortest path for any 2 nodes?

ReplyDeleteThx so much

@Jo, I guess you were talking about all-pair shortest paths (so that you might get shortest path between any two nodes).

ReplyDeleteWell, dijkstra won't be able to solve that easily, you could have run dijkstra once for each query.

But there are more straight forward ways to get that. Use floyed warshall or johnson's algorithms.

Floyed Warshall is very easy.

I keeping just for Dijkstra's Algorithm c++ codes and accidentally came here. I coded my assignment of Dijkstra's Algorithm in 2D array and i have problems implement it. Any idea or what good website gives sample codes of Dijkstra's Algorithm. The Dijkstra's i know how it works in paper, however when comes to coding, i'm not really good at it.

ReplyDeleteI have try to compile your code successfully, but i dont have the text file of in.txt. Please you show the file to run ur code.

Hi, forget the in.txt thing, if you look carefully, that line is disabled. All you need to do is just enter the input graph, follow this format:

ReplyDeleteFirst give two integers:

# of nodes: n and # of edges: e

Then e lines each containing and edge:

u v w where the edge is u<--->v having weight w

done!

If you want to use a directed graph, then look, in the input area, remove this line:

G[v].pb(pii(u, w));

Hope you can do it now, but actually I didn't believe what you have written, I mean, if you know C++ then this code is very easy to understand, at least anyone can determine the input format from it! and if you don't know the language or don't know how to implement dijkstra, that will be a clear cheating, don't do that, learn the hard way :)

Obfuscated code.... If this were an application that required collaboration you would be scolded.

ReplyDeleteSeriously the choice of variable names makes me want to strangle you.

I am afraid you are in a wrong place, this is no place for software developers and this NEVER will require collaboration. This program is PERFECTLY OK for contest programming. Anyways, thanks for visiting my blog :)

Delete@Anonymous::What the heck are you talking ? There can't be more neat and clean and accurate code than this. I will suggest you take some elementary school book and learn the topic "Coding Style". This higher level code is not for you..

ReplyDeleteGood post and Smart Blog

ReplyDeleteThanks for your good information and i hope to subscribe and visit my blog STD Symptoms and more Clinical Manifestations Granuloma Inguinale (Donovanosis) thanks again admin

Dear Zobayer:

ReplyDeleteYour code was very useful for a beginner like me to understand a C++ implementation of the Dijkstra algorithm. I have a silly question (I am a beginner). I would like to find the distance between the "starting" node and another node (let's call it "target", which we can be read in the beginning ), I don't need the entire distance D[i]. This should take less time on a large graph. So I thought I should just change the condition for while loop in your code to

while(!F[target]). Is that correct. I was getting nonsensical answers when I did that..could you please help?

Tarun

The only optimization you can do here is, between line 45 and 46, you can add the check, if(u == target) return d[u]; You cannot do anything other than this, because that will not ensure the correctness of dijkstra anymore. No matter whether you need or not, the nodes used in various paths between start and target must be calculated.

DeleteThanks for visiting my blog :)

Dijkstra algorithm is actually dynamic programming algorithm so before node n you must calculate minimum distance too all nodes <n otherwise u won't get correct answer

DeleteHi Zobayer,

ReplyDeleteThanks a lot for your code. I'm a beginner to C++, and this is very helpful.

I have one question about the speed to construct the graph. When I have a graph which has 1,000,000 nodes, and about 4,000,000 edges, this part"G[u].pb(pii(v, w))" takes a lot of time (e.g., 3s). Is there better way to make this part faster?

Thank you!

Yes there is. Just keep a list of the edges and maintain a link among the edges those who start from the same nodes. An example is in this post

Deletehttp://zobayer.blogspot.com/2010/05/maximum-flow-dinitz-algorithm.html

Just check how I maintained the graph. It's not hard to understand.

Thanks for visiting.

Hi Zobayer,

DeleteThank you for your reply.

I managed to roughly understand the list used to represent the graph. But my problem is, after I change my graph to that format, how can I still use the Dijkastra algorithm listed in this blog?

Thank you!

basically all you need to do is just change the loop in which adjacents to node u are traversed.

Deletebasically it is something like:

u = Q.top().first;

......

......

for(i=fin[u]; i>=0; i=next[i]) {

v = to[i]; // now work with v

......

......

I was wondering how to modify key in priority queue.

ReplyDeleteSolution you have presented is very clever and elegant.

I like it very much.

This is straight forward textbook implementation. I didn't do the clever thing myself either.

DeleteI will explain what I mean.

DeleteDuring relaxation you have to actualize elements in priority queue. How it can be done in STL priority queue?

You have some elements there, but you can only take minimal one and put another. There is no decrease-key operation.

In your or textbook (from which textbook?) implementation you just ignore old elements in priority queue, you are removing them later. That is clever and elegant for me :)

Thanks for replying, actually by textbook I meant conventional. What I wanted to do is to implement the min heap using stl priority queue. By definition, values I want most will be popped earlier, no matter how many old useless values are still on priority queue. They will be removed sooner or later as you have noticed. Basically this is very old code and now a days, we do not write like this. I mean the comp class is really not necessary when the datatype is generic. For example here, greater< pii > instead of comp in priority queue declaration would do the same thing with lesser hassle.

Deletewhat is the use of DEBUG function here??

ReplyDeletein what conditions will it run?

It's of no use to the algorithm itself. I use it to see values of some variables on specific point. If you set the macro on line 08 from if(0) to if(1), the debug lines will be printed.

Deleteblah blah blah.....

DeleteI can't understand line 13. Sorry I'm a beginner.

ReplyDeleteIts ok, just follow this link and read + try the examples. http://www.cplusplus.com/reference/stl/priority_queue/priority_queue/

DeleteThanks zobayer . Its very nice :)

ReplyDelete:D Always welcome!

DeleteGreat work Zobayer!

ReplyDeleteCould you help me to print all the nodes (in the right sequence) of the minimum path between two nodes (starting node and end node given).

Thanks a lot.

Steve

Hi Steve, printing the optimal path is not that hard. We have to add another array to keep track of the previous node.

DeleteLet pre[v] stores the node from which we have last updated node v. So in dijkstra function:

if(!F[v] && D[u]+w < D[v]) {

DEBUG printf(" %d,", v);

D[v] = D[u] + w;

pre[v] = u; // this line stores the fact that v is updated from u with optimal cost

Q.push(pii(v, D[v]));

}

Then we need to write another function that will print the optimal path:

void printPath(int src, int dst) { // src and dst are source and destination nodes

if(dst == src) {

printf("%d", dst);

return;

}

printPath(src, pre[dst]);

printf(" %d", dst);

}

So first call dijkstra for src and dst, then call this function. Don't forget to reset the pre[] array.

Hope its clear now :)

So I tried this with this text file:

ReplyDelete6 10

0 1 9

0 3 2

1 2 11

1 4 3

2 4 5

2 5 12

3 1 4

3 4 8

4 3 1

4 5 6

0

and it does not work correctly. The output states:

Node 1, min weight = 6

Node 2, min weight = 8

Node 3, min weight = 2

Node 4, min weight = 3

Node 5, min weight = 9

however this is not correct the correct output should be:

Node 1, min weight = 6

Node 2, min weight = 17

Node 3, min weight = 2

Node 4, min weight = 9

Node 5, min weight = 15

Many people have tested this code . It is more likely that you are doing something wrong

ReplyDeleteIs there any way to exclude the bool[] F from the code?

ReplyDeleteYes, there is. in fact we do not use the boolean array for flagging in dijkstra implementations. If you look carefully, when you are getting a u = Q.top().first; you can get w = Q.top().second before popping it. It is the weight of node u when the node was inserted in the queue and as we are using a min heap / priority queue, it is already the minimum possible value for u. And a few lines below, there you will see, whenever we can update the cost of node V from U, we update it in d[V]. so d[V] will always store the minimum possible value for node V. Now, the observation is, there can be multiple instances of the node U in Q at any given time. But we only want to expand from the minimum one, i.e. the first one that is popped from the Q. The flag array is using the exact same thing, it is just marking whether we already used node U or not. The same logic can be checked by testing if (w > d[u]) continue;. Becuse d[u] will always hold minimum for u, and if w (the one paired with u in the Q) is greater than d[u], then we are sure that we have already seen and traversed from u before.

DeleteThus you don't need that anymore.

#include

ReplyDeleteusing namespace std;

#define MAX 100000

struct comp {

bool operator() (const pair &a, const pair &b) {

return a.second > b.second;

}

};

void inp(int &x)

{

register int c = getchar_unlocked();

x = 0;

for(;(c<48 || c>57);c = getchar_unlocked());

for(;c>47 && c<58;c = getchar_unlocked())

{

x = (x<<1) + (x<<3) + c - 48;

}

}

map mapp;

int main(){

int m,n,i,j,u,v,w,src,dest,edges,testcases,t;

inp(t);

while(t--){

inp(m);

priority_queue,vector >,comp> PQ;

vector > vec[m+1];

for(i=0;idist(m+1,INT_MAX);

memset(visited,0,sizeof(visited));

dist[src]=0;

PQ.push(make_pair(src,0));

while(!(PQ.empty())){

u=PQ.top().first;

PQ.pop();

if(u==dest)

break;

for(i=0;i<vec[u].size();i++){

v=vec[u][i].first;

w=vec[u][i].second;

if(visited[v]==false && dist[u]+w<dist[v]){

dist[v]=dist[u]+w;

PQ.push(make_pair(v,dist[v]));

}

}

visited[u]=true;

}

printf("%d\n",dist[dest]);

}

printf("\n");

}

return 0;

}

I am getting Wrong Answer on Spoj, taking help from the above algorithm. Can you please please tell where I am going wrong?

AC now.. the priority queue should not be declared global :)

DeleteI think you should not use global operator override for known classes or primitive types.

Deleteits a great tutorial thanx .. :-)

ReplyDeleteGood Job Zobayer!

ReplyDeleteIs it possible to verify if a graph is disconnected with this algorithm?

Yes. Start from any node. Do not use "early returns" and when the algorithm stops, check distance array if every position has less than infinite.

DeleteWhhat do you mean by "early returns"? if(F[u]) continue; ?

Deleteno, sometimes when you run it for specific destination, then once the destination point is popped from the queue, you can return from dijkstra. in that case many other nodes can remain unexplored. I mentioned about this scenario which is not present in this code anyway.

Delete