Link copied to clipboard. Share away!

Dismiss

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**

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

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**

×