 Explore
Placement Prep Edit 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. 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  