Code For Dijkstra’s Algorithm In C++

/*

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

*/