Program to find the shortest path between two vertices in an undirected graph is discussed here. Given a graph, find the shortest path between the given source and destination nodes.

For example, consider the graph given below. We have to find the shortest path between vertices 1 and 5.

1 -> 0 -> 4 -> 5

1 -> 0 -> 2 -> 5

1 -> 2 -> 5

**Shortest path: 1 -> 2 -> 5****Number of edges: 2**

**Algorithm to find the shortest path between two vertices in an undirected graph**

- Input the graph.
- Input the source and destination nodes.
- Find the paths between the source and the destination nodes.
- Find the number of edges in all the paths and return the path having the minimum number of edges.

Program to find the shortest path between the two vertices in an undirected graph is given below.

// C++ program to find the shortest path between two vertexes

#include<bits/stdc++.h>

using namespace std;

// Function to finding minimum number of edges

int shortest_path(vector <int> edges[], int u, int v, int n)

{

// Keep track of visited nodes

vector<bool> visited(n, 0);

// Initialize initial distances as 0 for all nodes

vector<int> distance(n, 0);

queue <int> queue1;

distance[u] = 0;

queue1.push(u);

visited[u] = true;

while (!queue1.empty())

{

int x = queue1.front();

queue1.pop();

for (int i=0; i<edges[x].size(); i++)

{

if (visited[edges[x][i]])

continue;

// Update the distances

distance[edges[x][i]] = distance[x] + 1;

queue1.push(edges[x][i]);

visited[edges[x][i]] = 1;

}

}

return distance[v];

}

// Function to add the given edges of the graph

void add_edge_graph(vector <int> edges[], int u, int v)

{

edges[u].push_back(v);

edges[v].push_back(u);

}

int main()

{

char ch;

int n = 9;

vector <int> edges[9];

int a, b;

cout << “\nEnter the connections of the graph \n”;

do

{

cin >> a >> b;

cin >> ch;

add_edge_graph(edges, a, b);

}while(ch == ‘y’ || ch == ‘Y’);

add_edge_graph(edges, 0, 1);

int u = 0;

int v = 5;

cout << “\nMinimum number of edges : ” << shortest_path(edges, u, v, n) << endl;

return 0;

}