Home Lifestyle Dijkstra’s Algorithm Implementation with C++ program

Dijkstra’s Algorithm Implementation with C++ program

110
0

Dijkstra’s algorithm aka the shortest path algorithm is used to find the shortest path in a graph that covers all the vertices.

Algorithm:

• Initially Dset contains src
dist[s]=0 dist[v]= ∞
• Set Dset to initially empty
• While all the elements in the graph are not added to ‘Dset’

• A. Let ‘u’ be any vertex not in ‘Dset’ and has minimum label dist[u]
• B. Add ‘u’ to Dset
• C. Update the label of the elements adjacent to u
• For each vertex ‘v’ adjacent to u
• If ‘v’ is not in ‘Dset’ then
• If dist[u]+weight(u,v)<dist[v] then
• Dist[v]=dist[u]+weight(u,v)

Dijkstra Algorithm program using C++

``````#include<iostream>
#include<climits>     /*Used for INT_MAX*/
using namespace std;
#define vertex 7      /*It is the total no of verteices in the graph*/
int minimumDist(int dist[], bool Dset[])   /*A method to find the vertex with minimum distance which is not yet included in Dset*/
{
int min=INT_MAX,index;                 /*initialize min with the maximum possible value as infinity does not exist */
for(int v=0;v<vertex;v++)
{
if(Dset[v]==false && dist[v]<=min)
{
min=dist[v];
index=v;
}
}
return index;
}
void dijkstra(int graph[vertex][vertex],int src)
{
int dist[vertex];
bool Dset[vertex];
for(int i=0;i<vertex;i++)
{
dist[i]=INT_MAX;
Dset[i]=false;
}
dist[src]=0;
for(int c=0;c<vertex;c++)
{
int u=minimumDist(dist,Dset);
Dset[u]=true;
for(int v=0;v<vertex;v++)

{
if(!Dset[v] && graph[u][v] && dist[u]!=INT_MAX && dist[u]+graph[u][v]<dist[v])
dist[v]=dist[u]+graph[u][v];
}
}
cout<<"Vertex\t\tDistance from source"<<endl;
for(int i=0;i<vertex;i++)
{
char c=65+i;
cout<<c<<"\t\t"<<dist[i]<<endl;
}
}
int main()
{
int graph[vertex][vertex]={{0,5,3,0,0,0,0},{0,0,2,0,3,0,1},{0,0,0,7,7,0,0},{2,0,0,0,0,6,0},{0,0,0,2,0,1,0},{0,0,0,0,0,0,0},
{0,0,0,0,1,0,0}};
dijkstra(graph,0);
return 0;
}
``````

OUTPUT

``````

Vertex      Distance from source
A               0
B               5
C               3
D               9
E               7
F               8
G               6

``````