Dijkstra’s Algorithm C++ Program – Source Code

9 April 2011 1,481 views No Comment


#include<iostream.h>

int path[10];
class dijk
{
	int nodes,cost[10][10],dist[10],s[10],source,dest;
	public:
	dijk()
	{
		cout<<"enter no. of nodes\n";
		cin>>nodes;
	}

	void read();
	void dijkstras();
	void display();

};

void dijk::read()
{
	int i,j,val,edges,count=0;
	for(i=0;i<nodes;i++)
		for(j=0;j<nodes;j++)
			if(i==j)
				cost[i][j]=0;
			else
				cost[i][j]=9999;

	cout<<"\nenter no. of edges\n";
	cin>>edges;

	while(count<edges)
	{
		cout<<"enter Vertex Vi and Vj\n";
		cin>>i>>j;
		cout<<"enter cost along this edge\n ";
		cin>>val;
		cost[i][j]=cost[j][i]=val;
		count++;
	}
}

void dijk::dijkstras()
{
	int i,j,v1,v2,min;
	cout<<"enter source and then destination\n";
	cin>>source>>dest;
	for(i=0;i<nodes;i++)
	{
		dist[i]=cost1[i];
		s[i]=0;
		path[i]=source;
	}

	s1=1;

	for(i=1;i<nodes;i++)
	{
		min=9999;
		v1=-1;
		for(j=0;j<nodes;j++)
		{
			if(s[j]==0)
				if(dist[j]<min)
				{
					min=dist[j];
					v1=j;
				}
		}

		s[v1]=1;

		for(v2=0;v2<nodes;v2++)
			if(s[v2]==0)
				if(dist[v1]+cost[v1][v2]<dist[v2])
				{
					dist[v2]=dist[v1]+cost[v1][v2];
					path[v2]=v1;
				}
	}
}

void dijk::display()
{
	int i;
	cout<<"Shortest path between "<<source<<" and "<<dest<<" is: \n";

	for(i=dest;i!=source;i=path[i])
		cout<<i<<"<-";

	cout<<source;
	cout<<"\nthe length="<<dist[dest];
}
void main()
{

	dijk d;
	d.read();
	d.dijkstras();
	d.display();

}

/*

Output

enter no. of nodes
5

enter no. of edges
7
enter Vertex Vi and Vj
0
1
enter cost along this edge
 4
enter Vertex Vi and Vj
1
2
enter cost along this edge
 1
enter Vertex Vi and Vj
0
2
enter cost along this edge
 8
enter Vertex Vi and Vj
1
3
enter cost along this edge
 3
enter Vertex Vi and Vj
2
3
enter cost along this edge
 7
enter Vertex Vi and Vj
2
4
enter cost along this edge
 3
enter Vertex Vi and Vj
3
4
enter cost along this edge
 8
enter source and then destination
0
4
Shortest path between 0 and 4 is:
4<-2<-1<-0
the length=8*/