Challenge: Find the Shortest Path between Two Vertices
We've dealt with several graph traversals. Now, we'll find the shortest path traversal between two vertices.
We'll cover the following
Problem Statement #
Implement the int findMin(Graph g, int source, int destination)
function which will take a graph and two vertices, source and destination. The result will be the shortest path from source to destination.
Remember, the shortest path will contain the minimum number of edges.
Note: Shortest distance between the same source and destination vertex will be 0.
Note: Your program should return -1 if either source or destination node does not exist.
Input #
A directed graph, a source vertex, and a destination vertex.
Output #
Returns number of edges in the shortest path between source and destination.
Sample Input #
graph = {
0 - 1
0 - 2
0 - 3
3 - 5
5 - 4
2 - 4
}
source = 0
destination = 4
Sample Output #
2
Level up your interview prep. Join Educative to access 70+ hands-on prep courses.