/*

Note: Because of encoding problems the following code may not work. If it doesn’t work download the code from the following link. Right click on the link and click on ‘save target as ‘ and save the text file

Download the code: dijkstra.txt

*/

/*

Title: Dijkstra’s single source shortest path algorithm

Author: Vinodh Kumar B

Description:

adjMatric[][] : This array is used to store the adjacency matrix of the input graph

predecessor[] : This array is used to store the predecessor elements. predecessor[i] is the previous element in the path from source to current node i.

ex: If 1->2->4->3 is the shortest path from node1(source) to node 3. predecessor[3] is 4.

distance[] : This array will store the minimum distance from the source to corresponding node. It will be updated in each iteration in dijkstra’s algorithm.

mark[] — This array is used to mark the nodes as visited. mark[i] = true, This means node i is marked as visited.

source — source is the starting node from which we have to find out the shortest distance to all other nodes in the graph.

numOfVertices — The number of nodes in the graph.

Note: Node ranges will be 0 to numOfVertices-1

getClosestUnmarkedNode() : This method will return the closest unmarked node from the current marked node.

printPath(i) : This will print the path from source node to i in recursive manner

output() : This method will print paths to all nodes from source and their shortest distance

read() : This method will read the graph values from input

initialize() : This method will set the initial values of predecessor[] to -1 and

dijkstra() : This method will implement the dijkstra’s algorithm

*/

#include<iostream>

#define INFINITY 999

using namespace std;

class Graph

{

private:

int adjMatrix[15][15];

int predecessor[15],distance[15];

bool mark[15];

int source;

int numOfVertices;

public:

void read();

void initialize();

int getClosestUnmarkedNode();

void dijkstra();

void output();

void printPath(int);

};

void Graph::read()

{

cout<<“Enter the number of vertices of the graph(should be > 0)\n”;

cin>>numOfVertices;

//Number of vertices should always greater than zero

while(numOfVertices <= 0) {

cout<<“Enter the number of vertices of the graph(should be > 0)\n”;

cin>>numOfVertices;

}

//Read the adjacency matrix for the graph with +ve weights

cout<<“Enter the adjacency matrix for the graph\n”;

cout<<“To enter infinity enter “<<INFINITY<<endl;

for(int i=0;i<numOfVertices;i++) {

cout<<“Enter the (+ve)weights for the row “<<i<<endl;

for(int j=0;j<numOfVertices;j++) {

cin>>adjMatrix[i][j];

while(adjMatrix[i][j]<0) {

cout<<“Weights should be +ve. Enter the weight again\n”;

cin>>adjMatrix[i][j];

}

}

}

//read the source node from which the shortest paths to other nodes has to be found

cout<<“Enter the source vertex\n”;

cin>>source;

while((source<0) && (source>numOfVertices-1)) {

cout<<“Source vertex should be between 0 and “<<numOfVertices-1<<endl;

cout<<“Enter the source vertex again\n”;

cin>>source;

}

}

void Graph::initialize()

{

for(int i=0;i<numOfVertices;i++) {

mark[i] = false;

predecessor[i] = -1;

distance[i] = INFINITY;

}

distance

[/source]

= 0;

}

int Graph::getClosestUnmarkedNode()

{

int minDistance = INFINITY;

int closestUnmarkedNode;

for(int i=0;i<numOfVertices;i++) {

if((!mark[i]) && ( minDistance >= distance[i])) {

minDistance = distance[i];

closestUnmarkedNode = i;

}

}

return closestUnmarkedNode;

}

void Graph::dijkstra()

{

initialize();

int minDistance = INFINITY;

int closestUnmarkedNode;

int count = 0;

while(count < numOfVertices) {

closestUnmarkedNode = getClosestUnmarkedNode();

mark[closestUnmarkedNode] = true;

for(int i=0;i<numOfVertices;i++) {

if((!mark[i]) && (adjMatrix[closestUnmarkedNode][i]>0) ) {

if(distance[i] > distance[closestUnmarkedNode]+adjMatrix[closestUnmarkedNode][i]) {

distance[i] = distance[closestUnmarkedNode]+adjMatrix[closestUnmarkedNode][i];

predecessor[i] = closestUnmarkedNode;

}

}

}

count++;

}

}

void Graph::printPath(int node)

{

if(node == source)

cout<<node<<“..”;

else if(predecessor[node] == -1)

cout<<“No path from “<<source<<“to “<<node<<endl;

else {

printPath(predecessor[node]);

cout<<node<<“..”;

}

}

void Graph::output()

{

for(int i=0;i<numOfVertices;i++) {

if(i == source)

cout<<source<<“..”<<source;

else

printPath(i);

cout<<“->”<<distance[i]<<endl;

}

}

int main()

{

Graph G;

G.read();

G.dijkstra();

G.output();

return 0;

}

/*Sample output:

[vinod@thelegendbox cpp]$ g++ dijkstra.cpp

[vinod@thelegendbox cpp]$ ./a.out

Enter the number of vertices of the graph(should be > 0)

5

Enter the adjacency matrix for the graph

To enter infinity enter 999

Enter the (+ve)weights for the row 0

0

2

4

999

1

Enter the (+ve)weights for the row 1

2

0

7

3

999

Enter the (+ve)weights for the row 2

4

7

0

2

999

Enter the (+ve)weights for the row 3

999

3

2

0

6

Enter the (+ve)weights for the row 4

1

999

999

6

0

Enter the source vertex

0

0..0->0

0..1..->2

0..2..->4

0..1..3..->5

0..4..->1

*/

Thank you very much. This example is been a great help for my test.

Where can i find codes for Dijkstra and Bellman-Ford Algorithms in C++ or VisualC like this example?? Please help me!! Thanks.

ferhatkarakoyun@hotmail.com

good effort i will try it

thank you very much

Thanks a lot!! Really helps!!

Thank you!

Function Dijkstra(L[1..n, 1..n]): array [2..n] array D[2..n], P[2..n] C = {2, 3, …, n} for i = 2 to n do D[i] = L[1, i] P[i] = 1 repeat n – 2 times v = the index of the minimum D[v] not yet selected remove v from C // and implicitly add v to S for each w Î C do if (D[w] > D[v] + L[v, w]) then D[w] = D[v] + L[v, w] P[w] = v return D, P

//can convert this pseudocode for me by today 24/08/07???thanks u so much

pls make another program that will require the user to input exit node…. thank you poh!!! it helps us a lot in our case study…we need it before October 19.,can you pls make us a program?plsss..

can you pls send the source code in this address… help_us_pls66@yahoo.com…tnx…

Can you send this code in my e-mail please? I’m not able to see all the code here…Tks

i want to know the programming for shortest path using dijstra’s floyd’s algorithm

it not executing properly …..

how can i use this code

i can run but i don’t understand

hi;u have a nice site…

would u plz write a prog abt dfs and bfs traversal in graph with c++….i really need it as soon as possible

Thanks for the program dude

it really works !!!

Wow, for someone who has gone out of their way to post some nice code (thanks btw.) there sure are a lot of demanding people posting their “needs.” Aside from looking like kid trying to get someone else to do their work for them I humm… no sadly that’s what all these comments look like, aside from the odd thanks in there :).

pleas write Code For Dijkstra’s Algorithm In C#

The code is good I got it and it is so simple

thank u !!!!!!!!!!!!!!!!!

can you give me a some short of information about dijkstra

what is the application of dijkstra ?

plz email this information to me.

thank you very much in advance.

#########ashok rathod#######

Implement modified Dijkstra’s shortest paths algorithm that also gives the count of number of shortest paths to every node.

Input: The weighted (positive weights) directed graph

with node 1 considered as source is taken as input from a file the first line

having the size of the graph to be read (the size of the graph is dynamically set)

The file format:

n

adjacency matrix of size n

Output: The shortest paths from source to every node has to be printed along with the count of paths at that node.

hi is this program working 100% accurately????????

looking forward for an immediate help

thank you

thanks….

it really help us

Hi, Vikram

I really liked your blog very helpful and full of knowledge on different programming languages.

This program on Dijkstra is working fine on my machine, now the question is that can i implement “dijkstra algorithm of shortest path” in socket programming for routers.

Suppose there are 6 no. of routers and i want to send a data packet from source router to another.

Looking forward to hear from you.

Javed Akhtar

Hi, Vinod (apology for the wrong name in the previous comment)

I really liked your blog very helpful and full of knowledge on different programming languages.

This program on Dijkstra is working fine on my machine, now the question is that can i implement “dijkstra algorithm of shortest path” in socket programming for routers.

Suppose there are 6 no. of routers and i want to send a data packet from source router to another.

Looking forward to hear from you.

Javed Akhtar

Reply

Hi can you please explain what exactly is the source vertex?

ANd i would like to ask if you could help me to find a shortest path with specific nodes and vertex but with random weight for those that have weight !

Please email to me !

thank u

wah sweety………….,.

what to do for distances on line 69 where distance=0?

how can be a distance array intialized like distance=0????????????

it’s gives error for that reply soon………….

ha but very useful prg……

in lab sessions………

Please download the code from here

r u talking abt distance[ source ] =0

Vinod can you please upload the .txt file again? I have the encoding problem and the link to download the .txt does not work so I’m guessing you took it down.

~thanks in advance

🙂

Thanx a lot !!! 🙂 🙂 Was searching for it !!! 🙂

Thanks

great it helps alot

hi dude it does not work

what to do for distances on line 69 where distance=0?

how can be a distance array intialized like distance=0

distance[ source ] =0;

Read above.

🙂

Thanks man for this solution, but i didn’t get the last part when introducing the source vertex

Thanks in advance Vinod this was a huge help in my TSP assignment I’ve credited you for the implementation and I’ll modify it for my solutions.

Traveling Salesman Problem

thanks sir it really very helpfull for me……..

what does this mean?

————

distance

[/source]

= 0;

i think its to large

looking Easy to understand.Thank You.