## Dijkstra Algorithm – Finding Shortest Path

Dijkstra’s Algorithm is designed to determine the shortest routes between the source node and every other node in the network.

Algorithm:-

2. Initialize source node with a distance of 0 & all other nodes with infinite distance.
3. For each neighbor of source node, calculate the shortest distance between the current node’s distance and the distance to its neighbor.
• If the shortest distance is less than the distance of the other neighbor, then set that distance as the final shortest distance.
4. Continue step 3 until we’ve calculated all nodes’ shortest path to source.

So let’s take a look at how this Dijkstra Algorithm works in C++

```#include "iostream"
#include<conio.h>
#define INFINITY 99999
using namespace std;
class Dijkstra
{
private:
int graph;
int predecessor,dist;
bool mark;
int source;
int vertices;
public:
void input();
void initialize();
int search_min_node();
void calculate_dist();
void output();
void display_path(int);
};
void Dijkstra::input() {
cout<<"Enter the number of vertices of the graph(should be > 0)\n";
cin>>vertices;
while(vertices <= 0) {
cout<<"Enter the number of vertices of the graph(should be > 0)\n";
cin>>vertices;  }
cout<<"Enter the adjacency matrix for the graph\n";
cout<<"To enter infinity enter "<<INFINITY<<endl;
for(int i=1;i<=vertices;i++) {
cout<<"Enter the positive weights for the row "<<i<<endl;
for(int j=1;j<=vertices;j++) {
cin>>graph[i][j];
while(graph[i][j]<0) {
cout<<"Weights should be positive. Enter the weight again\n";
cin>>graph[i][j];
}  }  }
cout<<"Enter the source vertex\n";
cin>>source;
while((source<0) && (source>vertices-1)) {
cout<<"Source vertex should be between 0 and"<<vertices-1<<endl;
cout<<"Enter the source vertex again\n";
cin>>source;
}
}
void Dijkstra::initialize() {
for(int i=1;i<=vertices;i++) {
mark[i] = false;
dist[i] = INFINITY ;
predecessor[i] = -1;
}
dist[source]= 0;
}
int Dijkstra::search_min_node() {
int min_dist = INFINITY;
int closestUnmarkedNode;
for(int i=1;i<=vertices;i++) {
if((!mark[i]) && ( min_dist >= dist[i])) {
min_dist = dist[i];
closestUnmarkedNode = i;
}  }
return closestUnmarkedNode;
}
void Dijkstra::calculate_dist() {
initialize();
int minDistance = INFINITY;
int closestUnmarkedNode;
int count = 0;
while(count<vertices) {
closestUnmarkedNode = search_min_node();
mark[closestUnmarkedNode] = true;
for(int i=1;i<=vertices;i++) {
if((!mark[i]) && (graph[closestUnmarkedNode][i]>0) ) {
if(dist[i] > dist[closestUnmarkedNode]+graph[closestUnmarkedNode][i]) {
dist[i] = dist[closestUnmarkedNode]+graph[closestUnmarkedNode][i];
predecessor[i] = closestUnmarkedNode;
}  }  }
count++;  }
}
void Dijkstra::display_path(int node) {
if(node == source)
cout<<(char)(node + 65)<<"..";
else if(predecessor[node] == -1)
cout<<"No path from “<<source<<”to "<<(char)(node + 97)<<endl;
else {
display_path(predecessor[node]);
cout<<(char) (node+65)<<"..";
}
getch();
}
void Dijkstra::output() {
for(int i=1;i<=vertices;i++) {
if(i == source)
cout<<(char)(source + 65)<<".."<<source;
else
display_path(i);
cout<<"->"<<dist[i]<<endl;
}
getch();
}

int main()
{
Dijkstra a;
a.input();
a.calculate_dist();
a.output();
return 0;
}
```

## How this Dijkstra C++ Code Works?

Output  Of  This  Code. . .

Enter the number of vertices of the graph(should be > 0)

5

Enter the adjacency matrix for the graph

To enter infinity enter 99999

Enter the positive weights for the row 1

0 1 6 0 0

Enter the positive weights for the row 2

1 0 2 3 5

Enter the positive weights for the row 3

6 2 0 4 2

Enter the positive weights for the row 4

0 3 4 0 2

Enter the positive weights for the row 5

0 5 2 2 0

Enter the source vertex 1

•       B..1->0
•       B..C..->1
•       B..C..D..->3
•       B..C..E..->4
•       B..C..D..F..->5