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

Click here to learn more about FACE Prep PRO

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

@@coding::1@@

Recommended Programs

• Open and closed gates problem
• Number of Islands
• N digit numbers with digits in non-decreasing order
• Maximum number of As using four keys