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.

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 #


Level up your interview prep. Join Educative to access 70+ hands-on prep courses.