Solution: Find the Shortest Path between Two Vertices
The topic discusses finding the shortest path between two vertices in a directed graph using the Breadth-First Search (BFS) algorithm. It outlines the process of initializing visited and distance lists, utilizing a queue to traverse the graph, and updating distances until the destination node is reached or determined unreachable. The time complexity is O(V + E), where V is the number of vertices and E is the number of edges, while the space complexity is O(V) due to the storage of vertices in the queue and lists for tracking visited nodes and distances.
We'll cover the following...
Statement
Given a directed graph of n nodes and two vertices, src and dest, return the length of the shortest path between src and dest. The shortest path will contain the minimum number of edges.
If no path exists between src and dest, return -1.
Constraints:
-
n -
Node.data