AIM:
To implement a C++ program for Dijkstra’s Algorithm to find the shortest path algorithm.
To implement a C++ program for Dijkstra’s Algorithm to find the shortest path algorithm.
ALGORITHM:
Step 1: Include the header files
Step 2: Save the adjacency matrix in a file.
Step 3: Get as input the source node and destination node.
Step 4: Search the shortest path from source to destination.
Step 5: Initialize all the distances in the shortest path graph to infinity and all the nodes status to infinity.
Step 6: Start with the source node.
Step 7: Find the adjacent node and its shortest distance from the source node.
Step 8: Take the minimum distance value node and repeat step(7) till all the nodes become visited.
PROGRAM:
#include<iostream>
#define INFINITY 999
using namespace std;
class Dijkstra
{
private:
int adjMatrix[15][15];
int predecessor[15],distance[15];
bool mark[15]; //keep track of visited node
int source;
int numOfVertices;
public:
void read();
void initialize();
int getClosestUnmarkedNode();
void calculateDistance();
void output();
void printPath(int);
};
void Dijkstra::read()
{
cout<<"Enter the number of vertices of the graph(should be > 0)\n";
cin>>numOfVertices;
while(numOfVertices <= 0)
{
cout<<"Enter the number of vertices of the graph(should be > 0)\n";
cin>>numOfVertices;
}
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];
}
}
}
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 Dijkstra::initialize()
{
for(int i=0;i<numOfVertices;i++)
{
mark[i] = false;
predecessor[i] = -1;
distance[i] = INFINITY;
}
distance[source]= 0;
}
int Dijkstra::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 Dijkstra::calculateDistance()
{
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 Dijkstra::printPath(int node)
{
if(node == source)
cout<<(char)(node + 97)<<"..";
else if(predecessor[node] == -1)
cout<<"No path from “<<source<<”to "<<(char)(node + 97)<<endl;
else
{
printPath(predecessor[node]);
cout<<(char) (node + 97)<<"..";
}
}
void Dijkstra::output()
{
for(int i=0;i<numOfVertices;i++)
{
if(i == source)
cout<<(char)(source + 97)<<".."<<source;
else
printPath(i);
cout<<"->"<<distance[i]<<endl;
}
}
int main()
{
Dijkstra G;
G.read();
G.calculateDistance();
G.output();
return 0;
}
SAMPLE OUTPUT:
Enter the number of vertices of the graph(should be > 0)
6
Enter the adjacency matrix for the graph
To enter infinity enter 999
Enter the (+ve)weights for the row 0
0 4 2 999 999 999
Enter the (+ve)weights for the row 1
4 0 1 5 999 999
Enter the (+ve)weights for the row 2
2 1 0 8 10 999
Enter the (+ve)weights for the row 3
999 5 8 0 2 6
Enter the (+ve)weights for the row 4
999 999 10 2 0 3
Enter the (+ve)weights for the row 5
999 999 999 6 3 0
Enter the source vertex
0
a..0->0
a..c..b..->3
a..c..->2
a..c..b..d..->8
a..c..b..d..e..->10
a..c..b..b..e..f->13
RESULT:
Thus a C++ program for Dijkstra’s Algorithm to find the shortest path algorithm is implemented successfully.
No comments:
Post a Comment