# 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.

### 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;
} ```
[gravityforms id="5" description="false" titla="false" ajax="true"]