Intermediate Level
Implement the shortestPathUnweightedGraph method that returns the shortest distance between two nodes in an unweighted graph.
The input contains an unweighted graph, a start node, and an end node.
Your task is to return the length of the shortest path from start to end. Because every edge has the same weight, the path length is the number of edges used.
If the end node cannot be reached from the start node, return -1.
Example 1
Input
nodes (int) =
4edges (int[][]) =
[[0,1],[1,2],[2,3]]size (int) =
3start (int) =
0end (int) =
3Returns (int)
3Example 2
Input
nodes (int) =
3edges (int[][]) =
[[0,1],[1,2]]size (int) =
2start (int) =
0end (int) =
2Returns (int)
2Example 3
Input
nodes (int) =
3edges (int[][]) =
[[0,1]]size (int) =
1start (int) =
0end (int) =
2Returns (int)
-1Use breadth-first search because BFS visits nodes in increasing distance order in an unweighted graph.
Start from the given start node with distance 0. Visit all directly connected nodes with distance 1, then their neighbors with distance 2, and so on.
The first time the end node is reached, that distance is the shortest path. If BFS finishes without reaching the end node, return -1.
Pseudocode:
function shortestPathUnweightedGraph(nodes, edges, size, start, end):
graph = adjacency list for nodes
for each edge in edges:
u = edge[0]
v = edge[1]
add v to graph[u]
add u to graph[v]
queue = empty queue
visited = array filled with false
push (start, 0) into queue
visited[start] = true
while queue is not empty:
current, distance = remove front from queue
if current == end:
return distance
for each nextNode in graph[current]:
if visited[nextNode] == false:
visited[nextNode] = true
push (nextNode, distance + 1) into queue
return -1Ready to test your solutionRun Code checks your solution against the test cases.Shift + Enter to run