C++ Program to Find the Shortest Path Between Two Vertices Using Dijkstra’s Algorithm

This is a C++ Program to check whether path exists between two given nodes. The idea is to run the depth first search algorithm with the given source node, if during dfs we visit destination node, path exists, not otherwise.
Here is source code of the C++ Program to Find Whether a Path Exists Between 2 Given Nodes. The C++ program is successfully compiled and run on a Linux system. The program output is also shown below.

#include <iostream>
#include <list>

using namespace std;

// This class represents a directed graph using adjacency list representation
class Graph
{
int V; // No. of vertices
list *adj; // Pointer to an array containing adjacency lists
public:
Graph(int V); // Constructor
void addEdge(int v, int w); // function to add an edge to graph
bool isReachable(int s, int d); // returns true if there is a path from s to d
};

Graph::Graph(int V)
{
this->V = V;
adj = new list [V];
}

void Graph::addEdge(int v, int w)
{
adj[v].push_back(w); // Add w to v’s list.
}

// A BFS based function to check whether d is reachable from s.
bool Graph::isReachable(int s, int d)
{
// Base case
if (s == d)
return true;

// Mark all the vertices as not visited
bool *visited = new bool[V];
for (int i = 0; i < V; i++)
visited[i] = false;

// Create a queue for BFS
list queue;

// Mark the current node as visited and enqueue it
visited[s] = true;
queue.push_back(s);

// it will be used to get all adjacent vertices of a vertex
list::iterator i;

while (!queue.empty())
{
// Dequeue a vertex from queue and print it
s = queue.front();
queue.pop_front();

// Get all adjacent vertices of the dequeued vertex s
// If a adjacent has not been visited, then mark it visited
// and enqueue it
for (i = adj[s].begin(); i != adj[s].end(); ++i)
{
// If this adjacent node is the destination node, then return true
if (*i == d)
return true;

// Else, continue to do BFS
if (!visited[*i])
{
visited[*i] = true;
queue.push_back(*i);
}
}
}

return false;
}

// Driver program to test methods of graph class
int main()
{
// Create a graph given in the above diagram
Graph g(4);
g.addEdge(0, 1);
g.addEdge(0, 2);
g.addEdge(1, 2);
g.addEdge(2, 0);
g.addEdge(2, 3);
g.addEdge(3, 3);

cout << "Enter the source and destination vertices: (0-3)";
int u, v;
cin >> u >> v;
if (g.isReachable(u, v))
cout << "\nThere is a path from " << u << " to " << v;
else
cout << "\nThere is no path from " << u << " to " << v;

int temp;
temp = u;
u = v;
v = temp;
if (g.isReachable(u, v))
cout << "\nThere is a path from " << u << " to " << v;
else
cout << "\nThere is no path from " << u << " to " << v;

return 0;
}

Output:

$ g++ PathBetweenNodes.cpp
$ a.out

Enter the source and destination vertices: (0-3)
1 3

There is a path from 1 to 3
There is no path from 3 to 1

Enter the source and destination vertices: (0-3)
2 3

There is a path from 2 to 3
There is no path from 3 to 2

------------------
(program exited with code: 0)
Press return to continue

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

C++ Program to Find the Shortest Path from Source Vertex to All Other Vertices in Linear Time

This is a C++ Program to find the shortest path in linear time. This can be done by using Dijkstra’a Shortestpath algorithm.
Here is source code of the C++ Program to Find the Shortest Path from Source Vertex to All Other Vertices in Linear Time. The C++ program is successfully compiled and run on a Linux system. The program output is also shown below.

#include <stdio.h>
#include <limits.h>
#include <iostream>

using namespace std;

// Number of vertices in the graph
#define V 9

// A utility function to find the vertex with minimum distance value, from
// the set of vertices not yet included in shortest path tree
int minDistance(int dist[], bool sptSet[])
{
// Initialize min value
int min = INT_MAX, min_index;

for (int v = 0; v < V; v++)
if (sptSet[v] == false && dist[v] <= min)
min = dist[v], min_index = v;

return min_index;
}

// A utility function to print the constructed distance array
int printSolution(int dist[], int n)
{
cout << "Vertex Distance from Source\n";
for (int i = 0; i < V; i++)
printf("%d \t\t %d\n", i, dist[i]);
}

// Funtion that implements Dijkstra's single source shortest path algorithm
// for a graph represented using adjacency matrix representation
void dijkstra(int graph[V][V], int src)
{
int dist[V]; // The output array. dist[i] will hold the shortest
// distance from src to i

bool sptSet[V]; // sptSet[i] will true if vertex i is included in shortest
// path tree or shortest distance from src to i is finalized

// Initialize all distances as INFINITE and stpSet[] as false
for (int i = 0; i < V; i++)
dist[i] = INT_MAX, sptSet[i] = false;

// Distance of source vertex from itself is always 0
dist[src] = 0;

// Find shortest path for all vertices
for (int count = 0; count < V - 1; count++)
{
// Pick the minimum distance vertex from the set of vertices not
// yet processed. u is always equal to src in first iteration.
int u = minDistance(dist, sptSet);

// Mark the picked vertex as processed
sptSet[u] = true;

// Update dist value of the adjacent vertices of the picked vertex.
for (int v = 0; v < V; v++)

// Update dist[v] only if is not in sptSet, there is an edge from
// u to v, and total weight of path from src to v through u is
// smaller than current value of dist[v]
if (!sptSet[v] && graph[u][v] && dist[u] != INT_MAX && dist[u]
+ graph[u][v] < dist[v])
dist[v] = dist[u] + graph[u][v];
}

// print the constructed distance array
printSolution(dist, V);
}

int main()
{
int graph[V][V] =
{ { 0, 4, 0, 0, 0, 0, 0, 8, 0 }, { 4, 0, 8, 0, 0, 0, 0, 11, 0 }, {
0, 8, 0, 7, 0, 4, 0, 0, 2 },
{ 0, 0, 7, 0, 9, 14, 0, 0, 0 }, { 0, 0, 0, 9, 0, 10, 0, 0,
0 }, { 0, 0, 4, 0, 10, 0, 2, 0, 0 }, { 0, 0, 0, 14,
0, 2, 0, 1, 6 }, { 8, 11, 0, 0, 0, 0, 1, 0, 7 }, {
0, 0, 2, 0, 0, 0, 6, 7, 0 } };

dijkstra(graph, 0);

return 0;
}

Output

$ g++ LinearTimeShortestPath.cpp
$ a.out

Vertex Distance from Source
0 0
1 4
2 12
3 19
4 21
5 11
6 9
7 8
8 14

------------------
(program exited with code: 0)
Press return to continue

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

C++ Program to Use the Bellman-Ford Algorithm to Find the Shortest Path Between Two Vertices Assuming that Negative Size Edges Exist in the Graph



This is a C++ Program to find the shortest path algorithm using Bellman-Ford algorithm. This algorithm also entertains negative edge weights.
Here is source code of the C++ Program to Use the Bellman-Ford Algorithm to Find the Shortest Path Between Two Vertices Assuming that Negative Size Edges Exist in the Graph. The C++ program is successfully compiled and run on a Linux system. The program output is also shown below.

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <limits.h>

// a structure to represent a weighted edge in graph
struct Edge
{
int src, dest, weight;
};

// a structure to represent a connected, directed and weighted graph
struct Graph
{
// V-> Number of vertices, E-> Number of edges
int V, E;

// graph is represented as an array of edges.
struct Edge* edge;
};

// Creates a graph with V vertices and E edges
struct Graph* createGraph(int V, int E)
{
struct Graph* graph = (struct Graph*) malloc(sizeof(struct Graph));
graph->V = V;
graph->E = E;

graph->edge = (struct Edge*) malloc(graph->E * sizeof(struct Edge));

return graph;
}

// A utility function used to print the solution
void printArr(int dist[], int n)
{
printf("Vertex Distance from Source\n");
for (int i = 0; i < n; ++i)
printf("%d \t\t %d\n", i, dist[i]);
}

// The main function that finds shortest distances from src to all other
// vertices using Bellman-Ford algorithm. The function also detects negative
// weight cycle
void BellmanFord(struct Graph* graph, int src)
{
int V = graph->V;
int E = graph->E;
int dist[V];

// Step 1: Initialize distances from src to all other vertices as INFINITE
for (int i = 0; i < V; i++)
dist[i] = INT_MAX;
dist[src] = 0;

// Step 2: Relax all edges |V| - 1 times. A simple shortest path from src
// to any other vertex can have at-most |V| - 1 edges
for (int i = 1; i <= V - 1; i++)
{
for (int j = 0; j < E; j++)
{
int u = graph->edge[j].src;
int v = graph->edge[j].dest;
int weight = graph->edge[j].weight;
if (dist[u] != INT_MAX && dist[u] + weight < dist[v])
dist[v] = dist[u] + weight;
}
}

// Step 3: check for negative-weight cycles. The above step guarantees
// shortest distances if graph doesn't contain negative weight cycle.
// If we get a shorter path, then there is a cycle.
for (int i = 0; i < E; i++)
{
int u = graph->edge[i].src;
int v = graph->edge[i].dest;
int weight = graph->edge[i].weight;
if (dist[u] != INT_MAX && dist[u] + weight < dist[v])
printf("Graph contains negative weight cycle");
}

printArr(dist, V);

return;
}

// Driver program to test above functions
int main()
{
/* Let us create the graph given in above example */
int V = 5; // Number of vertices in graph
int E = 8; // Number of edges in graph
struct Graph* graph = createGraph(V, E);

// add edge 0-1 (or A-B in above figure)
graph->edge[0].src = 0;
graph->edge[0].dest = 1;
graph->edge[0].weight = -1;

// add edge 0-2 (or A-C in above figure)
graph->edge[1].src = 0;
graph->edge[1].dest = 2;
graph->edge[1].weight = 4;

// add edge 1-2 (or B-C in above figure)
graph->edge[2].src = 1;
graph->edge[2].dest = 2;
graph->edge[2].weight = 3;

// add edge 1-3 (or B-D in above figure)
graph->edge[3].src = 1;
graph->edge[3].dest = 3;
graph->edge[3].weight = 2;

// add edge 1-4 (or A-E in above figure)
graph->edge[4].src = 1;
graph->edge[4].dest = 4;
graph->edge[4].weight = 2;

// add edge 3-2 (or D-C in above figure)
graph->edge[5].src = 3;
graph->edge[5].dest = 2;
graph->edge[5].weight = 5;

// add edge 3-1 (or D-B in above figure)
graph->edge[6].src = 3;
graph->edge[6].dest = 1;
graph->edge[6].weight = 1;

// add edge 4-3 (or E-D in above figure)
graph->edge[7].src = 4;
graph->edge[7].dest = 3;
graph->edge[7].weight = -3;

BellmanFord(graph, 0);

return 0;
}

$ g++ BellmanFord.cpp
$ a.out

Vertex Distance from Source
0 0
1 -1
2 2
3 -2
4 1

------------------
(program exited with code: 0)
Press return to continue

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

C++ Program to Implement Shortest Path Algorithm for DAG Using Topological Sorting

This is a C++ Program to find shortest path for DAG using topological sorting. For a general weighted graph, we can calculate single source shortest distances in O(VE) time using Bellman–Ford Algorithm. For a graph with no negative weights, we can do better and calculate single source shortest distances in O(E + VLogV) time using Dijkstra’s algorithm. Can we do even better for Directed Acyclic Graph (DAG)? We can calculate single source shortest distances in O(V+E) time for DAGs. The idea is to use Topological Sorting.
Here is source code of the C++ Program to Implement Shortest Path Algorithm for DAG Using Topological Sorting. The C++ program is successfully compiled and run on a Linux system. The program output is also shown below.

// A C++ program to find single source shortest paths for Directed Acyclic Graphs
#include <iostream>
#include <list>
#include <stack>
#include <limits.h>

#define INF INT_MAX
using namespace std;

class AdjListNode
{
int v;
int weight;
public:
AdjListNode(int _v, int _w)
{
v = _v;
weight = _w;
}
int getV()
{
return v;
}
int getWeight()
{
return weight;
}
};

// Class to represent a graph using adjacency list representation
class Graph
{
int V; // No. of vertices'

// Pointer to an array containing adjacency lists
list *adj;

// A function used by shortestPath
void topologicalSortUtil(int v, bool visited[], stack &Stack);
public:
Graph(int V); // Constructor

// function to add an edge to graph
void addEdge(int u, int v, int weight);

// Finds shortest paths from given source vertex
void shortestPath(int s);
};

Graph::Graph(int V)
{
this->V = V;
adj = new list [V];
}

void Graph::addEdge(int u, int v, int weight)
{
AdjListNode node(v, weight);
adj[u].push_back(node); // Add v to u's list
}

void Graph::topologicalSortUtil(int v, bool visited[], stack &Stack)
{
// Mark the current node as visited
visited[v] = true;

// Recur for all the vertices adjacent to this vertex
list::iterator i;
for (i = adj[v].begin(); i != adj[v].end(); ++i)
{
AdjListNode node = *i;
if (!visited[node.getV()])
topologicalSortUtil(node.getV(), visited, Stack);
}

// Push current vertex to stack which stores topological sort
Stack.push(v);
}

void Graph::shortestPath(int s)
{
stack Stack;
int dist[V];

// Mark all the vertices as not visited
bool *visited = new bool[V];
for (int i = 0; i < V; i++)
visited[i] = false;

// Call the recursive helper function to store Topological Sort
// starting from all vertices one by one
for (int i = 0; i < V; i++)
if (visited[i] == false)
topologicalSortUtil(i, visited, Stack);

// Initialize distances to all vertices as infinite and distance
// to source as 0
for (int i = 0; i < V; i++)
dist[i] = INF;
dist[s] = 0;

// Process vertices in topological order
while (Stack.empty() == false)
{
// Get the next vertex from topological order
int u = Stack.top();
Stack.pop();

// Update distances of all adjacent vertices
list::iterator i;
if (dist[u] != INF)
{
for (i = adj[u].begin(); i != adj[u].end(); ++i)
if (dist[i->getV()] > dist[u] + i->getWeight())
dist[i->getV()] = dist[u] + i->getWeight();
}
}

// Print the calculated shortest distances
for (int i = 0; i < V; i++)
(dist[i] == INF) ? cout << "INF " : cout << dist[i] << " ";
}

// Driver program to test above functions
int main()
{
// Create a graph given in the above diagram. Here vertex numbers are
// 0, 1, 2, 3, 4, 5 with following mappings:
// 0=r, 1=s, 2=t, 3=x, 4=y, 5=z
Graph g(6);
g.addEdge(0, 1, 5);
g.addEdge(0, 2, 3);
g.addEdge(1, 3, 6);
g.addEdge(1, 2, 2);
g.addEdge(2, 4, 4);
g.addEdge(2, 5, 2);
g.addEdge(2, 3, 7);
g.addEdge(3, 4, -1);
g.addEdge(4, 5, -2);

int s = 1;
cout << "Following are shortest distances from source " << s << " \n";
g.shortestPath(s);

return 0;
}

Output:

$ g++ ShortestPathDAG.cpp
$ a.out

Following are shortest distances from source 1
INF 0 2 6 5 3
------------------
(program exited with code: 0)
Press return to continue

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

C++ Program to Find All_Pairs_Shortest_Path

This C++ Program to Find All Pairs Shortest Path in a Graph.
Here is source code of the C++ Program to Find All Pairs Shortest Path using Floyd’s Algorithm. The C++ program is successfully compiled and run on a Linux system. The program output is also shown below.

/*
* C++ Program to Find All Pairs Shortest Path
*/
#include <iostream>
#include <cstdlib>

#define max 10
#define infi 999
using namespace std;
int p[max][max];
/*
* All Pairs Shortest Path using Floyd's Algorithm
*/
void allpairshort(int a[max][max], int n)
{
int k, i, j;
for (k = 0; k < n; k++)
{
for (i = 0; i < n; i++)
{
for (j = 0; j < n; j++)
{
if (a[i][k] + a[k][j] < a[i][j])
{
a[i][j] = a[i][k] + a[k][j];
p[i][j] = k;
}
}
}
}
}

/*
* Storing the shortest path
*/
void shortest(int i, int j)
{
int k = p[i][j];
if (k > 0)
{
shortest(i, k);
cout<<" "< shortest(k, j);
}
}
/*
* Display the Shortest Path
*/
void findpath(int a[max][max], int i, int j, int n)
{
cout<<"Path from " << i <<" to "<< j << ":";
if (a[i][j] < infi)
{
cout<<" "< shortest(i, j);
cout<<" "< }
}
/*
* Main Contains Menu
*/
int main()
{
int i, j;
int a[][10] = {{0, 10, infi, 30, 100},
{infi, 0 , 50, infi, infi},
{infi, infi , 0, infi, 10},
{infi, infi , 20, 0, 60},
{infi, infi , infi, infi, 0},
};

allpairshort(a, 5);
findpath(a, 0, 4, 5);
return 0;
}

$ g++ allpairshortestpath.cpp
$ a.out
Path from 0 to 4: 0 3 2 4

------------------
(program exited with code: 1)
Press return to continue

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

C++ Program to Implement Dijkstra’s Algorithm Using Queue

This is a C++ Program to implement Dijkstra’s Shortest path algorithm using Queue.
Here is source code of the C++ Program to Implement Dijkstra’s Algorithm Using Queue. The C++ program is successfully compiled and run on a Linux system. The program output is also shown below.

#include <cstdio>
#include <queue>
#include <vector>
#include <iostream>

using namespace std;

#define MAX 100001
#define INF (1<<20)
#define pii pair< int, int >
#define pb(x) push_back(x)

struct comp
{
bool operator()(const pii &a, const pii &b)
{
return a.second > b.second;
}
};

priority_queue , comp> Q;
vector G[MAX];
int D[MAX];
bool F[MAX];

int main()
{
int i, u, v, w, sz, nodes, edges, starting;

// create graph
cout << "Enter the number of vertices and edges: ";
cin >> nodes >> edges;
cout << "Enter the edges with weigth: : \n";
for (i = 0; i < edges; i++)
{
cin >> u >> v >> w;
G[u].pb(pii(v, w));
G[v].pb(pii(u, w)); // for undirected
}
cout << "Enter the source node: ";
cin >> starting;

// initialize distance vector
for (i = 1; i <= nodes; i++)
D[i] = INF;
D[starting] = 0;
Q.push(pii(starting, 0));

// dijkstra
while (!Q.empty())
{
u = Q.top().first;
Q.pop();
if (F[u])
continue;
sz = G[u].size();
for (i = 0; i < sz; i++)
{
v = G[u][i].first;
w = G[u][i].second;
if (!F[v] && D[u] + w < D[v])
{
D[v] = D[u] + w;
Q.push(pii(v, D[v]));
}
}
F[u] = 1; // done with u
}

// result
for (i = 1; i <= nodes; i++)
cout << "Node " << i << ", min weight = " << D[i] << endl;
return 0;
}

Output:

$ g++ DijkstraUsingQueue.cpp
$ a.out

Enter the number of vertices and edges: 6
7
Enter the edges with weigth: :
0 1 1
1 2 3
1 4 5
3 4 7
4 5 9
5 3 8
0 3 3
Enter the source node: 1
Node 1, min weight = 0
Node 2, min weight = 3
Node 3, min weight = 12
Node 4, min weight = 5
Node 5, min weight = 14
Node 6, min weight = 1048576

------------------
(program exited with code: 0)
Press return to continue

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

C++ Program to Implement Dijkstra’s Algorithm using Priority_queue(Heap)

This C++ program displays the Djikstra’s Algorithm of finding shortest paths from one node to others using the concept of a priority queue. a priority queue is an abstract data type which is like a regular queue or stack data structure, but where additionally each element has a “priority” associated with it.
Here is the source code of the C++ program to display the shortest distance and the source node associated with the shortest distance. This C++ program is successfully compiled and run on DevCpp,a C++ compiler.The program output is given below.

/*
* C++ Program to Implement Dijkstra's Algorithm using Priority_queue(Heap)
*/
#include <iostream>
#include <stdio.h>

using namespace std;

#include <conio.h>
#define INFINITY 999
struct node
{
int cost;
int value;
int from;
}a[7];
void min_heapify(int *b, int i, int n)
{
int j, temp;
temp = b[i];
j = 2 * i;
while (j <= n)
{
if (j < n && b[j + 1] < b[j])
{
j = j + 1;
}
if (temp < b[j])
{
break;
}
else if (temp >= b[j])
{
b[j / 2] = b[j];
j = 2 * j;
}
}
b[j / 2] = temp;
return;
}
void build_minheap(int *b, int n)
{
int i;
for(i = n / 2; i >= 1; i--)
{
min_heapify(b, i, n);
}
}
void addEdge(int am[][7], int src, int dest, int cost)
{
am[src][dest] = cost;
return;
}
void bell(int am[][7])
{
int i, j, k, c = 0, temp;
a[0].cost = 0;
a[0].from = 0;
a[0].value = 0;
for (i = 1; i < 7; i++)
{
a[i].from = 0;
a[i].cost = INFINITY;
a[i].value = 0;
}
while (c < 7)
{
int min = 999;
for (i = 0; i < 7; i++)
{
if (min > a[i].cost && a[i].value == 0)
{
min = a[i].cost;
}
else
{
continue;
}
}
for (i = 0; i < 7; i++)
{
if (min == a[i].cost && a[i].value == 0)
{
break;
}
else
{
continue;
}
}
temp = i;
for (k = 0; k < 7; k++)
{
if (am[temp][k] + a[temp].cost < a[k].cost)
{
a[k].cost = am[temp][k] + a[temp].cost;
a[k].from = temp;
}
else
{
continue;
}
}
a[temp].value = 1;
c++;
}
cout<<"Cost"<<"\t"<<"Source Node"< for (j = 0; j < 7; j++)
{
cout << a[j].cost << "\t"< }
}
int main()
{
int n, am[7][7], c = 0, i, j, cost;
for (int i = 0; i < 7; i++)
{
for (int j = 0; j < 7; j++)
{
am[i][j] = INFINITY;
}
}
while (c < 12)
{
cout<<"Enter the source, destination and cost of edge\n";
cin>>i>>j>>cost;
addEdge(am, i, j, cost);
c++;
}
bell(am);
getch();
}

Output

Enter the source, destination and cost of edge
0
1
3
Enter the source, destination and cost of edge
0
2
6
Enter the source, destination and cost of edge
1
2
2
Enter the source, destination and cost of edge
1
3
4
Enter the source, destination and cost of edge
2
3
1
Enter the source, destination and cost of edge
2
4
4
Enter the source, destination and cost of edge
2
5
2
Enter the source, destination and cost of edge
3
4
2
Enter the source, destination and cost of edge
3
6
4
Enter the source, destination and cost of edge
4
6
1
Enter the source, destination and cost of edge
4
5
2
Enter the source, destination and cost of edge
5
6
1
Cost Source Node
0 0
3 0
5 1
6 2
8 3
7 2
8 5

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

C++ Program to Implement Dijkstra’s Algorithm Using Set

This is a C++ Program to find shortest path. Dijkstra’s algorithm is very similar to Prim’s algorithm for minimum spanning tree. Like Prim’s MST, we generate a SPT (shortest path tree) with given source as root. We maintain two sets, one set contains vertices included in shortest path tree, other set includes vertices not yet included in shortest path tree. At every step of the algorithm, we find a vertex which is in the other set (set of not yet included) and has minimum distance from source.
Below are the detailed steps used in Dijkstra’s algorithm to find the shortest path from a single source vertex to all other vertices in the given graph.
Algorithm
1) Create a set sptSet (shortest path tree set) that keeps track of vertices included in shortest path tree, i.e., whose minimum distance from source is calculated and finalized. Initially, this set is empty.
2) Assign a distance value to all vertices in the input graph. Initialize all distance values as INFINITE. Assign distance value as 0 for the source vertex so that it is picked first.
3) While sptSet doesn’t include all vertices
….a) Pick a vertex u which is not there in sptSetand has minimum distance value.
….b) Include u to sptSet.
….c) Update distance value of all adjacent vertices of u. To update the distance values, iterate through all adjacent vertices. For every adjacent vertex v, if sum of distance value of u (from source) and weight of edge u-v, is less than the distance value of v, then update the distance value of v.
Here is source code of the C++ Program to Implement Dijkstra’s Algorithm Using Set. The C++ program is successfully compiled and run on a Linux system. The program output is also shown below.

// A C++ program for Dijkstra's single source shortest path algorithm.
// The program is for adjacency matrix representation of the graph

#include <stdio.h>
#include <limits.h>

// Number of vertices in the graph
#define V 9

// A utility function to find the vertex with minimum distance value, from
// the set of vertices not yet included in shortest path tree
int minDistance(int dist[], bool sptSet[])
{
// Initialize min value
int min = INT_MAX, min_index;

for (int v = 0; v < V; v++)
if (sptSet[v] == false && dist[v] <= min)
min = dist[v], min_index = v;

return min_index;
}

// A utility function to print the constructed distance array
int printSolution(int dist[], int n)
{
printf("Vertex Distance from Source\n");
for (int i = 0; i < V; i++)
printf("%d \t\t %d\n", i, dist[i]);
}

// Funtion that implements Dijkstra's single source shortest path algorithm
// for a graph represented using adjacency matrix representation
void dijkstra(int graph[V][V], int src)
{
int dist[V]; // The output array. dist[i] will hold the shortest
// distance from src to i

bool sptSet[V]; // sptSet[i] will true if vertex i is included in shortest
// path tree or shortest distance from src to i is finalized

// Initialize all distances as INFINITE and stpSet[] as false
for (int i = 0; i < V; i++)
dist[i] = INT_MAX, sptSet[i] = false;

// Distance of source vertex from itself is always 0
dist[src] = 0;

// Find shortest path for all vertices
for (int count = 0; count < V - 1; count++)
{
// Pick the minimum distance vertex from the set of vertices not
// yet processed. u is always equal to src in first iteration.
int u = minDistance(dist, sptSet);

// Mark the picked vertex as processed
sptSet[u] = true;

// Update dist value of the adjacent vertices of the picked vertex.
for (int v = 0; v < V; v++)

// Update dist[v] only if is not in sptSet, there is an edge from
// u to v, and total weight of path from src to v through u is
// smaller than current value of dist[v]
if (!sptSet[v] && graph[u][v] && dist[u] != INT_MAX && dist[u]
+ graph[u][v] < dist[v])
dist[v] = dist[u] + graph[u][v];
}

// print the constructed distance array
printSolution(dist, V);
}

// driver program to test above function
int main()
{
/* Let us create the example graph discussed above */
int graph[V][V] =
{ { 0, 4, 0, 0, 0, 0, 0, 8, 0 }, { 4, 0, 8, 0, 0, 0, 0, 11, 0 }, {
0, 8, 0, 7, 0, 4, 0, 0, 2 },
{ 0, 0, 7, 0, 9, 14, 0, 0, 0 }, { 0, 0, 0, 9, 0, 10, 0, 0,
0 }, { 0, 0, 4, 0, 10, 0, 2, 0, 0 }, { 0, 0, 0, 14,
0, 2, 0, 1, 6 }, { 8, 11, 0, 0, 0, 0, 1, 0, 7 }, {
0, 0, 2, 0, 0, 0, 6, 7, 0 } };

dijkstra(graph, 0);

return 0;
}


Output:

$ g++ DijkstraUsingSet.cpp
$ a.out

Vertex Distance from Source
0 0
1 4
2 12
3 19
4 21
5 11
6 9
7 8
8 14
------------------
(program exited with code: 0)
Press return to continue

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
C++ Program to Implement Bellmanford Algorithm

This C++ program implements the Bellmanford Algorithm is an algorithm that computes shortest paths from a single source vertex to all of the other vertices in a weighted digraph.
Here is the source code of the C++ program to display the shortest path costs along with the intermediate node paths taken on giving the source node, destination node and cost of node as inputs. This C++ program is successfully compiled and run on DevCpp, a C++ compiler. The program output is given below.

/*
* C++ Program to Implement Bellmanford Algorithm
*/
#include <iostream>
#include <stdio.h>

using namespace std;

#include <conio.h>
#define INFINITY 999
struct node
{
int cost;
int value;
int from;
}a[5];
void addEdge(int am[][5],int src,int dest,int cost)
{
am[src][dest] = cost;
return;
}
void bell(int am[][5])
{
int i, j, k, c = 0, temp;
a[0].cost = 0;
a[0].from = 0;
a[0].value = 0;
for (i = 1; i < 5; i++)
{
a[i].from = 0;
a[i].cost = INFINITY;
a[i].value = 0;
}
while (c < 5)
{
int min = 999;
for (i = 0; i < 5; i++)
{
if (min > a[i].cost && a[i].value == 0)
{
min = a[i].cost;
}
else
{
continue;
}
}
for (i = 0; i < 5; i++)
{
if (min == a[i].cost && a[i].value == 0)
{
break;
}
else
{
continue;
}
}
temp = i;
for (k = 0; k < 5; k++)
{
if (am[temp][k] + a[temp].cost < a[k].cost)
{
a[k].cost = am[temp][k] + a[temp].cost;
a[k].from = temp;
}
else
{
continue;
}
}
a[temp].value = 1;
c++;
}
cout<<"Cost"<<"\t"<<"Source Node"< for (j = 0; j < 5; j++)
{
cout << a[j].cost << "\t"< }
}
int main()
{
int n, am[5][5], c = 0, i, j, cost;
for (int i = 0; i < 5; i++)
{
for (int j = 0; j < 5; j++)
{
am[i][j] = INFINITY;
}
}
while (c < 8)
{
cout<<"Enter the source, destination and cost of edge\n";
cin>>i>>j>>cost;
addEdge(am, i, j, cost);
c++;
}
bell(am);
getch();
}

Output

Enter the source, destination and cost of edge
0
1
-1
Enter the source, destination and cost of edge
0
2
4
Enter the source, destination and cost of edge
1
2
3
Enter the source, destination and cost of edge
1
3
2
Enter the source, destination and cost of edge
3
1
1
Enter the source, destination and cost of edge
1
4
2
Enter the source, destination and cost of edge
4
3
-3
Enter the source, destination and cost of edge
3
2
5
Cost Source Node
0 0
-1 0
2 1
-2 4
1 1

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

C++ Program to Implement Floyd-Warshall Algorithm

This C++ program displays the shortest path traversal from a particular node to every other node present inside the graph relative to the former node.
Here is the source code of the C++ program of the Floyd Warshall Algoritm of finding shortest paths from any node in graph to every other node with the shortest path length displayed beside each pair of vertices. This C++ program is successfully compiled and run on DevCpp, a C++ compiler. The program output is given below.

/*
* C++ Program to Implement Floyd-Warshall Algorithm
*/
#include <iostream>
#include <conio.h>

using namespace std;
void floyds(int b[][7])
{
int i, j, k;
for (k = 0; k < 7; k++)
{
for (i = 0; i < 7; i++)
{
for (j = 0; j < 7; j++)
{
if ((b[i][k] * b[k][j] != 0) && (i != j))
{
if ((b[i][k] + b[k][j] < b[i][j]) || (b[i][j] == 0))
{
b[i][j] = b[i][k] + b[k][j];
}
}
}
}
}
for (i = 0; i < 7; i++)
{
cout<<"\nMinimum Cost With Respect to Node:"< for (j = 0; j < 7; j++)
{
cout << b[i][j] <<"\t";
}

}
}
int main()
{
int b[7][7];
cout<<"ENTER VALUES OF ADJACENCY MATRIX\n\n";
for (int i = 0; i < 7; i++)
{
cout<<"enter values for "<<(i+1)<<" row"< for (int j = 0; j < 7; j++)
{
cin>>b[i][j];
}
}
floyds(b);
getch();
}

Output
ENTER VALUES OF ADJACENCY MATRIX

enter values for 1 row
0
3
6
0
0
0
0
enter values for 2 row
3
0
2
4
0
0
0
enter values for 3 row
6
2
0
1
4
2
0
enter values for 4 row
0
4
1
0
2
0
4
enter values for 5 row
0
0
4
2
0
2
1
enter values for 6 row
0
0
2
0
2
0
1
enter values for 7 row
0
0
0
4
1
1
0

Minimum Cost With Respect to Node:0
0 3 5 6 8 7 8
Minimum Cost With Respect to Node:1
3 0 2 3 5 4 5
Minimum Cost With Respect to Node:2
5 2 0 1 3 2 3
Minimum Cost With Respect to Node:3
6 3 1 0 2 3 3
Minimum Cost With Respect to Node:4
8 5 3 2 0 2 1
Minimum Cost With Respect to Node:5
7 4 2 3 2 0 1
Minimum Cost With Respect to Node:6
8 5 3 3 1 1 0

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

C++ Program to Implement Johnson’s Algorithm

This is a C++ Program to implement Johnson’s Algorithm. Johnson’s algorithm helps to find shortest path between given source and destination nodes.
Here is source code of the C++ Program to Implement Johnson’s Algorithm. The C++ program is successfully compiled and run on a Linux system. The program output is also shown below.

#include <iostream>
#include <conio.h>

using namespace std;

int min(int a, int b);
int cost[10][10], a[10][10], i, j, k, c;

int min(int a, int b)
{
if (a < b)
return a;
else
return b;
}

int main(int argc, char **argv)
{
int n, m;
cout << "Enter no of vertices";
cin >> n;
cout << "Enter no of edges";
cin >> m;
cout << "Enter the\nEDGE Cost\n";
for (k = 1; k <= m; k++)
{
cin >> i >> j >> c;
a[i][j] = cost[i][j] = c;
}
for (i = 1; i <= n; i++)
for (j = 1; j <= n; j++)
{
if (a[i][j] == 0 && i != j)
a[i][j] = 31999;
}
for (k = 1; k <= n; k++)
for (i = 1; i <= n; i++)
for (j = 1; j <= n; j++)
a[i][j] = min(a[i][j], a[i][k] + a[k][j]);
cout << "Resultant adj matrix\n";
for (i = 1; i <= n; i++)
{
for (j = 1; j <= n; j++)
{
if (a[i][j] != 31999)
cout << a[i][j] << " ";
}
cout << "\n";
}
return 0;
}

Output:

$ g++ JohnsonsShortestPath.cpp
$ a.out

Enter no of vertices 3
Enter no of edges 5
Enter the
EDGE Cost
1 2 4
2 1 6
1 3 11
3 1 3
2 3 2
Resultant adj matrix
0 4 6
5 0 2
3 7 0

------------------
(program exited with code: 0)
Press return to continue

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

C++ Program to Find SSSP(Single Source Shortest Path) in DAG(Directed Acyclic Graphs)

This C++ program displays the shortest path traversal from a particular node to every other node present inside the graph relative to the former node.
Here is the source code of the C++ program of the Djikstra’s Algoritm of finding shortest paths from the first node in graph to every other node with the shortest path length displayed beside each pair of vertices.This C++ program is successfully compiled and run on DevCpp,a C++ compiler.The program output is given below.

/*
* C++ Program to find SSSP(Single Source Shortest Path)
* in DAG(Directed Acyclic Graphs)
*/
#include <iostream>
#include <conio.h>

using namespace std;
#define INFINITY 999
struct node
{
int from;
}p[7];
int c = 0;
void djikstras(int *a,int b[][7],int *dv)
{
int i = 0,j,min,temp;
a[i] = 1;
dv[i] = 0;
p[i].from = 0;
for (i = 0; i < 7;i++)
{
if (b[0][i] == 0)
{
continue;
}
else
{
dv[i] = b[0][i];
p[i].from = 0;
}
}
while (c < 6)
{
min = INFINITY;
for (i = 0; i < 7; i++)
{
if (min <= dv[i] || dv[i] == 0 || a[i] == 1)
{
continue;
}
else if (min > dv[i])
{
min = dv[i];
}
}
for (int k = 0; k < 7; k++)
{
if (min == dv[k])
{
temp = k;
break;
}
else
{
continue;
}
}
a[temp] = 1;
for (j = 0; j < 7; j++)
{
if (a[j] == 1 || b[temp][j] == 0)
{
continue;
}
else if (a[j] != 1)
{
if (dv[j] > (dv[temp] + b[temp][j]))
{
dv[j] = dv[temp] + b[temp][j];
p[i].from = temp;
}
}
}
c++;
}
for (int i = 0; i < 7; i++)
{
cout<<"from node "< }
}
int main()
{
int a[7];
int dv[7];
for(int k = 0; k < 7; k++)
{
dv[k] = INFINITY;
}
for (int i = 0; i < 7; i++)
{
a[i] = 0;
}
int b[7][7];
for (int i = 0;i < 7;i++)
{
cout<<"enter values for "<<(i+1)<<" row"< for(int j = 0;j < 7;j++)
{
cin>>b[i][j];
}
}
djikstras(a,b,dv);
getch();
}

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~