Graph Breadth First Search Depth First Search Shortest Path Minimum Spanning Tree
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) = 4
edges (int[][]) = [[0,1],[1,2],[2,3]]
size (int) = 3
start (int) = 0
end (int) = 3
Return:
(int) 3
Example 2
Input:
nodes (int) = 3
edges (int[][]) = [[0,1],[1,2]]
size (int) = 2
start (int) = 0
end (int) = 2
Return:
(int) 2
Example 3
Input:
nodes (int) = 3
edges (int[][]) = [[0,1]]
size (int) = 1
start (int) = 0
end (int) = 2
Return:
(int) -1

Use 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 -1
Run your code to see the result.