Explore
ProGrad Programs
Placement Prep
TCS Codevita
Live Placement Training
Live Aptitude Training
Live Programming Training
Webinars
About Us

Edit
Reply




Edit

Find the shortest path between two vertices in an undirected graph | FACE Prep

Published on 11 Mar 2020

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.

shortest path between two vertices in a graph

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


C++

Output
Input - Enter the connection of the graph 0 1 y 0 7 y 1 7 y 1 2 y 2 3 y 2 5 y 2 8 y 3 4 y 3 5 y 4 5 y 5 6 y 6 7 y 7 8 n Output - Minimum number of edges : 3


Recommended Programs





If you have any feedback about this article and want to improve this, please write to enquiry@faceprep.in
Explore 'c plus plus'
Articles Practice Exercises