Shortest path algorithms are used to find the shortest path between two vertices in a graph.

Shortest Path Algorithms for several types of Graphs such as:

1. Shortest Path in unweighted graph.

2. Shortest Path in weighted graph [Dijkstra’s]

3. Shortest Path in unweighted graph with negative edges.

4. Shortest Path in unweighted graph:

It is similar to BFS (Breadth First Search) Algorithm. BFS is a graph traversal technique, and it is used to find the shortest path in an unweighted graph between source node and the destination node with fewest number of edges.

It finds its applications in real life such as it is used in Snakes and Ladders game to find the least number of turns to reach the final path.

An unordered map named as parent is also created in which we will store parent as key and their children as value while visiting a particular node. The map will be later used to find the Shortest Path.

In the above illustration we can see that if we start from src (source) node 1, there are multiple paths possible to reach dest (destination) node 8 but there exists only one shortest path that has least number of edges out of the other two paths. Hence the shortest path has been printed along with its length.

APPROACH:

To print the shortest path, we make use of the unordered map named as parent. While visiting a particular node, we store that node as the Key and its father (father refers to that node from which its neighboring nodes are iterated in adjacency list) as Value in the parent map. While for src node both Key and Value are same in parent map because it is the starting point.

At the end, when all the nodes are visited, iterate through the parent map to print the shortest path.

In this algorithm we are calling BFS by passing two arguments that is src node and destination node.

CODE:

#include

#include

#include<unordered_map>

#include

using namespace std;

class Graph {

public:

unordered_map<int, list > adj;

void addEdge(int u,int v,bool bidir=true) {

adj[u].push_back(v);

if(bidir==true) {

adj[v].push_back(u);

}

}

//BFS ALGORTIHM:

void bfs(int src, int dest){

unordered_map <int, bool> visited;

unordered_map <int, int> parent;

queue q;

q.push(src);

visited[src] = true;

parent[src] = src;

while(!q.empty()) {

int father = q.front();

q.pop();

for (auto ch : adj[father]) {

if (! visited[ch]) {

visited[ch] = true;

parent[ch] = father;

q.push(ch);

}

}

}

//To print the shortest path:

int length = 0;

cout<<"Shortest Path from Source to Destination:"<<endl;

while (dest != parent[dest]) {

cout<<dest<<"<--";

dest = parent[dest];

length ++;

}

cout<<dest<<endl;

cout<<"Shortest Path Length: "<<length<<endl;

}

};

int main () {

//Creation of graph as shown in the illustration

Graph g;

g.addEdge(7,8);

g.addEdge(6,7);

g.addEdge(5,8);

g.addEdge(6,4);

g.addEdge(3,8);

g.addEdge(2,5);

g.addEdge(1,2);

g.addEdge(1,3);

g.addEdge(1,4);

g.bfs(1,8);

}

1. Shortest Path in weighted graph [Dijkstra’s]:

Dijkstra’s Algorithm is a graph search algorithm used to find the shortest path between source (src) node and all the other nodes in a weighted graph.

**

**

Two maps and a set data structure for implementing this algorithm.

One map will be named as distance in which Key will be nodes and their corresponding values will store the distance from source node to that node.

Another map will be named as parent, and it will be used to store the father of a node while iterating through a child node.