Shortest Path Visiting All Nodes – Python Solution

Navigate to Other Solutions

Problem Description

So, you think you can navigate a graph like a pro? Welcome to the “Shortest Path Visiting All Nodes” problem on LeetCode, where you get to play the role of a graph explorer! Imagine you’re a tourist in a city with a bunch of attractions (nodes) connected by roads (edges). Your mission is to visit every single attraction in the shortest possible time. Sounds easy, right? Well, buckle up, because this is where the fun begins!

You’re given a graph represented as an adjacency list, and your task is to find the shortest path that visits every node at least once. Think of it as trying to visit every ice cream shop in town without doubling back too much—because who has time for that?

Code Solution


class Solution:
    def shortestPathLength(self, graph: list[list[int]]) -> int:
        n = len(graph)
        goal = (1 << n) - 1
        q = collections.deque()  # (u, state)
        seen = set()

        for i in range(n):
            q.append((i, 1 << i))

        step = 0
        while q:
            for _ in range(len(q)):
                u, state = q.popleft()
                if state == goal:
                    return step
                if (u, state) in seen:
                    continue
                seen.add((u, state))
                for v in graph[u]:
                    q.append((v, state | 1 << v))
            step += 1

        return -1

Approach Explanation

The code uses a breadth-first search (BFS) approach to explore all possible paths in the graph. It maintains a queue to track the current node and the state of visited nodes. The goal is to reach a state where all nodes have been visited, represented by a bitmask. Each time a node is visited, it updates the state and checks if all nodes have been covered. If so, it returns the number of steps taken.

Time and Space Complexity

Complexity Type	Complexity
Time Complexity	O(N * 2^N), where N is the number of nodes.
Space Complexity	O(N * 2^N) due to the storage of states in the queue and the seen set.

Real-World Example

Imagine you’re a delivery driver tasked with delivering packages to every house in a neighborhood. You want to minimize your driving distance while ensuring that every house gets its package. This problem is akin to the "Shortest Path Visiting All Nodes" problem, where you need to find the most efficient route to cover all destinations without unnecessary detours.