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 find_min()
function which will take a directed graph and two vertices, A and B. The result will be the shortest path from A to B.
Remember, the shortest path will contain the minimum number of edges.
Input
A directed graph, a vertex A and a vertex B.
Output
Returns number of edges in the shortest path between A and B.
Sample input
graph = {
0 -> 1
0 -> 2
0 -> 3
3 -> 5
5 -> 4
2 -> 4
}
Vertex A = 0
Vertex B = 4
Sample output
2
Take a look at the illustration below to understand better.
Level up your interview prep. Join Educative to access 70+ hands-on prep courses.