Shortest Path Visiting All Nodes Solution in Java

Navigate to Other Solutions

Problem Description

Ah, the classic “Shortest Path Visiting All Nodes” problem! Imagine you’re a tourist in a city with a bunch of attractions (nodes) and you want to visit each one without getting lost. Sounds easy, right? Well, throw in some one-way streets (edges) and suddenly you’re questioning your life choices. The goal is to find the shortest path that allows you to visit every attraction at least once. It’s like trying to find the quickest route to all your friends’ houses for a party, but instead of fun, you just end up with a headache and a lot of “Are we there yet?” questions.

Code Solution


class Solution {
  public int shortestPathLength(int[][] graph) {
    final int n = graph.length;
    final int goal = (1 << n) - 1;
    Queue> q = new ArrayDeque<>(); // (u, state)
    boolean[][] seen = new boolean[n][1 << n];

    for (int i = 0; i < n; ++i)
      q.offer(new Pair<>(i, 1 << i));

    for (int step = 0; !q.isEmpty(); ++step)
      for (int sz = q.size(); sz > 0; --sz) {
        final int u = q.peek().getKey();
        final int state = q.poll().getValue();
        if (state == goal)
          return step;
        if (seen[u][state])
          continue;
        seen[u][state] = true;
        for (final int v : graph[u])
          q.offer(new Pair<>(v, state | 1 << v));
      }

    return -1;
  }
}

Approach Explanation

The code uses a breadth-first search (BFS) approach to explore all possible paths through 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, the corresponding bit in the state is set. The process continues until all nodes are visited, and the number of steps taken is returned.

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 the visited states.

Real-World Example

Imagine you're a delivery driver trying to deliver 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 each house represents a node, and the roads between them are the edges. The solution helps you find the most efficient route to ensure timely deliveries without backtracking unnecessarily.