C++ Program to Implement Dijkstra's Shortest Path Algorithm

Dijkstra's Shortest Path Algorithm

Dijkstra's shortest path Algorithm is a Greedy Algorithm and like Prim's Algorithm.

Dijkstra's Algorithm finds the shortest path having lower cost in a Graph. Dijkstra's Algorithm understands the Single Source Shortest Path issue for a Graph.

Steps to calculate the shortest path : 1) Create a set sp(shortest path)that monitors vertices incorporated into the shortest path tree, i.e., whose base separation from the source is determined and concluded. At first, this set is Null. 2) Assign a distance cost to all vertices in the i/p graph. Instate all distance value as Infinity. Appoint distance cost as 0 for the source vertex so it is picked first. 3) While sp does exclude all vertices a) Pick a vertex u which isn't there in sp and has least distance value. b) Include u to sp. c) Update distance value of all adjacent vertices of u. To refresh the distance values, iterate through all adjacent vertices. For each adjacent vertex v, if total of distance value of u (from source) and weight of edge u-v, is not exactly the distance value of v, at that point update the distance value of v.

C++ Program to Implement Dijkstra's Shortest Path Algorithm

#include<iostream>

using namespace std;

int N;

int graph[10][10];

int dist[10];

bool visited[10];

int parent[10];

void createGraph()

{

   int i,j,max,u,v,w;

   cout<<"Enter the number of nodes : ";

   cin>>N;

   for(i=0;i<=N;i++)

   for(j=0;j<=N;j++)

   graph[i][j]=0;

   max=N*(N+1);

   for(i=0;i<max;i++)

   {

   cout<<"Enter Edge and Weight : ";

   cin>>u>>v>>w;

   if(u==-1)    break;

   else

   {

       graph[u][v]=w;

       graph[v][u]=w;

   }

   }

}

int minDistance()

{

   int min = 10000, minDist;

   for (int v = 0; v < N; v++)

       if (visited[v] == false && dist[v] <= min)

       {

           min = dist[v];

           minDist = v;

       }

   return minDist;

}

void printPath(int j)

{

   if (parent[j]==-1)

       return;

   printPath(parent[j]);

   cout<<j<<" ";

}

void dijkstra()

{

   int src;

   cout<<"Enter the Source Node : ";

   cin>>src;

   for (int i = 0; i < N; i++)

   {

       parent[0] = -1;

       dist[i] = 10000;

       visited[i] = false;

   }

   dist[src] = 0;

   for (int count = 0; count < N-1; count++)

   {

       int u = minDistance();

       visited[u] = true;

       for (int v = 0; v < N; v++)

           if (!visited[v] && graph[u][v] &&

               dist[u] + graph[u][v] < dist[v])

           {

               parent[v] = u;

               dist[v] = dist[u] + graph[u][v];

           }

   }

   cout<<"Src->Dest\tDistance\tPath"<<endl;

   for (int i = 1; i < N; i++)

   {

       cout<<src<<"->"<<i<<"\t\t"<<dist[i]<<"\t\t"<<src<<" ";

       printPath(i);

       cout<<endl;

   }

}

int main()

{

   createGraph();

   dijkstra();

   return 0;

}

OUTPUT

Enter the number of nodes : 5

Enter Edge and Weight : 0 1 3

Enter Edge and Weight : 1 2 4

Enter Edge and Weight : 1 3 2

Enter Edge and Weight : 0 3 7

Enter Edge and Weight : 2 3 5

Enter Edge and Weight : 3 4 4

Enter Edge and Weight : 2 4 6

Enter Edge and Weight : -1 -1 -1

Enter the Source Node : 0

Src->Dest       Distance Path

0->1             3                0 1

0->2             7                 0 1 2

0->3             5                 0 1 3

0->4             9                0 1 3 4



You must be also searching for these programming languages :

• C++ Program To Implement Manchester and Differential Manchester Encoding

• C++ Program To Implement Go Back N

• C++ program to Implement Stop and Wait Flow Control Protocol

• C++ Program to Implement Cyclic Redundancy Code

• C++ Program To Implement Hamming Code

tags : Shortest Path Algorithm, Shortest Path, Dijkstra's Shortest Path Algorithm, Learn C++ Programs, Computer Networks, Computer Network Programming Language.