In this tutorial, we will discuss how to find the shortest path in an unweighted graph. In an unweighted graph, no edges have weight or all edges have the same weight.
In this problem, We will have a graph and 2 nodes, a source node, and a destination node. We have to print the shortest path from source to destination. The shortest path is a path where we have to visit the least number of nodes to go from the source node to the destination node. We will use BFS. If you don’t know how BFS works, read Breadth First Search Algorithm (BFS).
Finding the shortest path in an unweighted graph
We will maintain a queue, visited list, and parent list.
- Start by putting the source node in the queue, adding it to the visited list, and making its parent to itself.
- take the front node from the queue. let’s say it is r. Traverse through its adjacent node. If any of its adjacents is not visited put it in the back of the queue and make its parent r and add it to the visited list.
- Repeat step 2 until the queue is empty.
- Initialize a list of paths.
- put the destination node to the paths.
- Find the parent of the last added node of paths and put it to the paths.
- Repeat 6 until the parent of the last node is itself.
- print the paths in reverse order.
Finding the shortest path in an unweighted graph using C++
#include<bits/stdc++.h>
using namespace std;
int main()
{
int n,m;
cin>>n; // n is the number of vertices
cin>>m; // m is the number of edges
vector<vector<int> > adj(n); // n vector for each node
// input edgelist
for(int i=0;i<m;i++)
{
int a, b;
cin>>a>>b;
adj[a].push_back(b);
adj[b].push_back(a);
}
int source, destination;
cin>>source; // input source node
cin>>destination; // input destination node
vector<int> visited(n), parent(n);
queue<int> q;
q.push(source);
visited=1;
parent=source;
while(!q.empty())
{
int r=q.front();
q.pop();
for(auto it:adj[r])
{
if(visited[it]==0)
{
q.push(it);
visited[it]=1;
parent[it]=r;
}
}
}
if(visited[destination]==0)
{
cout<<"There is no path between node "<<source<<" to "<<destination<<endl;
return 0;
}
vector<int> path;
path.push_back(destination);
while(parent[path.back()]!=path.back())
{
path.push_back(parent[path.back()]);
}
reverse(path.begin(),path.end());
for(auto it:path)
{
cout<<it<<" ";
}
cout<<endl;
return 0;
}This is a C++ program that finds the shortest path between two nodes in an undirected graph using a breadth-first search (BFS) algorithm.
The program first takes input for the number of vertices and edges in the graph. Then, it creates an adjacency list to store the edges. Each vertex is represented as a vector and the vectors are stored in a vector container. The program takes input for each edge and adds them to the adjacency list.
Next, the program takes input for the source and destination nodes. It initializes a vector ‘visited’ to store whether each vertex is visited or not during the BFS traversal. It also initializes a vector ‘parent’ to store the parent node of each vertex during the traversal.
The program then starts the BFS traversal from the source node. It adds the source node to a queue and marks it as visited. It also sets its parent as itself. While the queue is not empty, it dequeues a node and explores its neighbors. If a neighbor has not been visited before, it adds it to the queue, marks it as visited, and sets its parent as the current node.
After the BFS traversal is complete, the program checks if the destination node is visited or not. If it is not visited, it means there is no path between the source and destination nodes. Otherwise, it constructs the path from the destination node to the source node by following the parent nodes from the destination node to the source node. The path is stored in a vector ‘path’ and is printed in reverse order to obtain the correct order of nodes in the path.
Discover more Python tips and elevate your coding skills with our comprehensive guide, “Python Beginner to Advanced.” Whether you’re a beginner or an experienced developer, this book covers everything from basic concepts to advanced techniques. And if you’re interested in expanding your programming collection, don’t miss out on our “Java Beginner to Advanced” guide as well!
Finding the shortest path in an unweighted graph using Python
from collections import deque
adj=[]
n=int(input()) # number of vertices.
m=int(input()) # number of edges
for i in range(n):
adj.append([])
# input edge list.
for i in range(m):
a, b=map(int, input().split())
adj[a].append(b)
adj[b].append(a)
source=int(input()) # input source node
destination=int(input()) # input destination node
path=[]
dq=deque()
visited=[0 for i in range(n)]
parent=[0 for i in range(n)]
visited=1
parent=source
while dq:
r=dq[0]
dq.popleft()
for i in adj[r]:
if visited[i]==0:
visited[i]=1
dq.append(i)
parent[i]=r
path.append(destination)
while parent[path[-1]]!=path[-1]:
path.append(parent[path[-1]])
path=path[::-1]
print(path)This is a Python code that finds the shortest path between a given source and destination node in an undirected graph using Breadth First Search (BFS).
First, it takes input of the number of vertices and edges in the graph and creates an adjacency list to store the edges. Then it takes the input of the source and destination nodes.
The code then initializes a deque (double-ended queue) with the source node and starts a BFS traversal. In each iteration, it dequeues the node at the front of the deque and explores its adjacent nodes. If an unvisited adjacent node is found, it marks it as visited, enqueues it, and updates its parent to the dequeued node.
After the traversal is completed, the code constructs the path from the source to the destination node by following the parent nodes starting from the destination until the source is reached. Finally, it prints the path.
