Shortest path in an unweighted graph

Problem Statement

Given the directed, connected and unweighted graph G, a Source and a Destination and the task to find the shortest path possible between two given vertices in the graph.

Note: The path does not contain any cycle which means path have finite number of vertices.

Example Input

Expected Output

Path : 0 3 

Implementation in C++

#include <bits/stdc++.h> 
using namespace std; 

void insert_vert(vector<int> Graph[], int Source, int Destination) 
{ 
	Graph[Source].push_back(Destination); 
	Graph[Destination].push_back(Source); 
} 

bool BreadthFirstsearch(vector<int> Graph[], int Source, int Destination, int vert, 
		int Result1[]) 
{ 
	list<int> Store; 

	bool Check_visited[vert]; 

	for (int i = 0; i < vert; i++) { 
		Check_visited[i] = false; 
		Result1[i] = -1; 
	} 

	Check_visited[Source] = true; 
	Store.push_back(Source); 

	while (!Store.empty()) { 
		int u = Store.front(); 
		Store.pop_front(); 
		for (int i = 0; i < Graph[u].size(); i++) { 
			if (Check_visited[Graph[u][i]] == false) { 
				Check_visited[Graph[u][i]] = true; 
				Result1[Graph[u][i]] = u; 
				Store.push_back(Graph[u][i]); 

				if (Graph[u][i] == Destination) 
					return true; 
			} 
		} 
	} 

	return false; 
} 

void Print_Short_Path(vector<int> Graph[], int srt, 
						int Destination, int vert) 
{ 
	int Result1[vert]; 

	if (BreadthFirstsearch(Graph, srt, Destination, vert, Result1) == false) { 
		return; 
	} 

	vector<int> Sort_Path; 
	int Path = Destination; 
	Sort_Path.push_back(Path); 
	while (Result1[Path] != -1) { 
		Sort_Path.push_back(Result1[Path]); 
		Path = Result1[Path]; 
	} 

	cout << "Path : "; 
	for (int i = Sort_Path.size() - 1; i >= 0; i--) 
		cout << Sort_Path[i] << " "; 
} 

// Main program
int main() 
{ 
	int vert = 4; 

	vector<int> Graph[vert]; 

	insert_vert(Graph, 0, 1); 
	insert_vert(Graph, 0, 2); 
	insert_vert(Graph, 0, 3); 
	insert_vert(Graph, 1, 3); 
	insert_vert(Graph, 2, 1); 
	insert_vert(Graph, 2, 3); 
	
	int source = 0, Destination = 3; 
	
	Print_Short_Path(Graph, source, Destination, vert); 
	return 0; 
} 
Scroll to Top
[gravityforms id="5" description="false" titla="false" ajax="true"]