Dijkstra’s Shortest Path Algorithm is popular algorithm for finding shortest path between different nodes. The algorithm (Pseudo Code) is as follows
procedure Dijkstra (G): weighted connected simple graph, with all weights positive)
[G has vertices a = v0, v1, ..... , vn = z and weights w(v1, v2) where w(vi, vj) = INFINITY if [vi, vj] is not an edge in G]
for i := 1 to n
L(vi) := INFINITY
L(a) := 0
S := NULL
[ the labels are now initialized so that the label of a is 0
and all other labels are INIFINITY, S is empty set]
while z is not belongs to S
begin
u := a vertex not in S with L(u) minimal
S := S U [u]
for all vertices u not in S
If L(u) + w(u,v) < L(v) then L(v) := L(u) + w(u,v)
[this adds a vertex to S with minimal label and updates the labels
vertices no in S]
end [L(z) = length of a shortest path from a to z]
Example:
Now lets come to an example which further illustrates above algorithm. Consider a weighted graph
Here a, b, c .. are nodes of the graph and the number between nodes are weights (distances) of the graph. Now we are going to find the shortest path between source (a) and remaining vertices. The adjacency matrix of the graph is
Now the following source code implements the above example
#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:
/** Function read() reads No of vertices, Adjacency Matrix and source
* Matrix from the user. The number of vertices must be greather than
* zero, all members of Adjacency Matrix must be postive as distances
* are always positive. The source vertex must also be positive from 0
* to noOfVertices - 1*/
void read();
/** Function initialize initializes all the data members at the begining of
* the execution. The distance between source to source is zero and all other
* distances between source and vertices are infinity. The mark is initialized
* to false and predecessor is initialized to -1*/
void initialize();
/** Function getClosestUnmarkedNode returns the node which is nearest from the
* Predecessor marked node. If the node is already marked as visited, then it search
* for another node.*/
int getClosestUnmarkedNode();
/** Function calculateDistance calculates the minimum distances from the source node to
* Other node.
void calculateDistance();
/** Function output prints the results
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;
}
The output of above program is
Post A Comment:
0 comments: