DEV Community

Shahrouz Nikseresht
Shahrouz Nikseresht

Posted on

Day 67: Python Shortest Path in Unweighted Graph - BFS Queue Magic for O(V+E) Routing Mastery (LeetCode Vibes)

#challenge #python #algorithms #datastructures

Welcome to Day 67 of the #80DaysOfChallenges journey! This intermediate challenge implements Breadth-First Search (BFS) to find the shortest path in an unweighted graph, using a queue for level-order traversal and a parent dict for path reconstruction, achieving optimal O(V+E) time where V is vertices and E edges. It handles dict adjacency for graphs, deque for efficient FIFO, and reconstructs the actual path list, making it essential for routing, networking, or game AI like maze solving. If you're advancing from basic queues to graph algorithms or prepping for interviews with shortest path questions (LeetCode #1129 style), this "Python BFS shortest path" script demonstrates a function that's robust, reconstructs paths, and easy to adapt for weighted graphs or distances.

💡 Key Takeaways from Day 67: BFS Shortest Path Function

This task features a function that uses BFS to explore levels, track parents for backtracking, and return the path list or None. It's a standard BFS pattern: enqueue start, dequeue/visit/enqueue neighbors, use parent for path. We'll detail: function with queue and parent dict, loop for traversal and enqueue, and path reconstruction with main demo.

1. Function Design: Queue, Visited, Parent Setup

The shortest_path_bfs function takes graph dict, start, target, returns path list:

def shortest_path_bfs(graph: dict, start, target):
    """Return the shortest path from start to target using BFS."""
    queue = deque([start])          # queue for BFS traversal
    visited = {start}               # track visited nodes
    parent = {start: None}          # store parent to reconstruct path
Enter fullscreen mode Exit fullscreen mode

Deque for O(1) popleft/append. Visited set prevents revisits. Parent dict tracks came-from for path build.

2. Loop Processing: Dequeue, Check Target, Enqueue Neighbors

Core while explores:

    while queue:
        node = queue.popleft()      # process next node in BFS order

        if node == target:
            break                   # shortest path found

        for neighbor in graph.get(node, []):
            if neighbor not in visited:
                visited.add(neighbor)       # mark as visited
                parent[neighbor] = node     # record where we came from
                queue.append(neighbor)      # add to BFS queue
Enter fullscreen mode Exit fullscreen mode

Popleft dequeues, breaks on target (BFS guarantees shortest). Enqueues unvisited neighbors, sets parent. graph.get(node, []) handles isolates.

3. Path Reconstruction: Backtrack from Target

After loop, build path:

    # reconstruct path if target was reached
    if target not in parent:
        return None

    path = []
    curr = target
    while curr is not None:
        path.append(curr)
        curr = parent[curr]

    return path[::-1]               # reverse path (start -> target)
Enter fullscreen mode Exit fullscreen mode

If target not reached, None. Else backtrack append, reverse for start-to-target.

4. Main Demo: Defined Graph and Print

Demo with dict graph:

graph = {
    "A": ["B", "C"],
    "B": ["D", "E"],
    "C": ["F"],
    "D": [],
    "E": ["F"],
    "F": []
}

start_node = "A"
target_node = "F"

print("Graph:", graph)
print(f"Finding shortest path from {start_node} to {target_node}")

path = shortest_path_bfs(graph, start_node, target_node)

if path is None:
    print("No path found.")
else:
    print(f"Shortest path: {path}")
    print(f"Path length: {len(path) - 1}")
Enter fullscreen mode Exit fullscreen mode

Prints graph, runs BFS from A to F, shows path like ['A', 'C', 'F'], length 2.

🎯 Summary and Reflections

This BFS shortest path uses queue for levels, parent for reconstruction. It reinforced:

  • BFS for unweighted shortest: Levels guarantee minimal steps.
  • Parent tracking: Essential for path, not just distance.
  • Get for neighbors: Handles missing keys gracefully.

Reflections: Add distance with level counter. For graphs, visited prevents cycles.

Advanced Alternatives: Dijkstra for weights. A* with heuristics. Multi-source BFS. Your path find? Share!

🚀 Next Steps and Resources

Day 67 routed graphs efficiently. In #80DaysOfChallenges? Weighted? Post!

Top comments (0)