DSA Master Logo
DSAMaster
Sign InSign Up
mediumDesignPattern: Design

Shortest Path in Unweighted Graph Solution

Problem Statement

Given a graph represented as an adjacency list, where keys are node identifiers (integers) and values are lists of adjacent node identifiers, find the shortest path between two specified nodes. Return a list of node identifiers representing the shortest path from the start node to the end node. If no path exists, return an empty list. The graph is unweighted, meaning each edge has a cost of 1.

Examples

Example 1:
Input:{"graph":{"0":["1","2"],"1":["0","3","4"],"2":["0","5"],"3":["1"],"4":["1","5"],"5":["2","4"]},"startNode":"0","endNode":"5"}
Output:["0","2","5"]
Explanation: The shortest path from node '0' to node '5' is 0 -> 2 -> 5, with a length of 2 edges.
Example 2:
Input:{"graph":{"A":["B","C"],"B":["A","D"],"C":["A","E"],"D":["B"],"E":["C"]},"startNode":"A","endNode":"D"}
Output:["A","B","D"]
Explanation: The shortest path from node 'A' to node 'D' is A -> B -> D, with a length of 2 edges.
Example 3:
Input:{"graph":{"1":["2"],"2":["3"],"3":["4"],"4":[]},"startNode":"1","endNode":"5"}
Output:[]
Explanation: There is no path from node '1' to node '5' because node '5' does not exist in the graph and there is no connection to it.

Constraints

  • The number of nodes in the graph is between 0 and 1000.
  • Node identifiers are strings.
  • The start and end nodes are guaranteed to be strings.
  • The graph can be disconnected.
Time: O(V + E) Space: O(V)
The optimal approach is to use Breadth-First Search (BFS). BFS explores the graph level by level, guaranteeing that the first time the end node is reached, it is via the shortest path. We use a queue for traversal and a dictionary to store the parent of each node to reconstruct the path.

Run, Test & Submit Code

Ready to practice this challenge? Launch our interactive compilation environment with compiler validation.

Solve on Interactive Workspace

Tested Solutions

from collections import deque def shortest_path_in_unweighted_graph(graph, start_node, end_node): if not graph: return [] if start_node == end_node: return [start_node] queue = deque([[start_node]]) visited = {start_node} while queue: current_path = queue.popleft() current_node = current_path[-1] if current_node not in graph: continue for neighbor in graph[current_node]: if neighbor not in visited: visited.add(neighbor) new_path = list(current_path) new_path.append(neighbor) if neighbor == end_node: return new_path queue.append(new_path) return []