CODEWITHSUNDEEP
algorithmgraphpathshortest-path
MyiEye
MyiEye

Reputation: 482

Shortest path to visit all nodes

I'm looking for an algorithm that seems very typical to me, but it seems that the common solutions are all just a little bit different.

In an undirected graph, I want the shortest path that visits every node. Nodes can be revisited and I do not have to return to the start node.

The Travelling Salesman Problem seems to add the restriction that each node can only be visited once and that the path has to return to where it started.

Minimal Spanning Trees may be part of a solution, but such algorithms only provide the tree, not a minimal path. Additionally, because they're trees and therefore have no loops, they force backtracking where a loop may be more efficient.

Upvotes: 21

Views: 19781

Answers (2)

Harry
Harry

Reputation: 11648

We can use a modified BFS.

Basically from any node during a BFS we need to be able to traverse nodes already travelled but how do we make sure we're not forming infinite cycles.

We store visited state for "ALL" nodes from each node, what this means is if we've walked over node 1 and we need to traverse back over it we can as long as our total state of "ALL" nodes has not been seen before. This is the reason for the bitmask and not a simple Set of Integers. Note you can use a Set of Strings to store the state as well it just runs a slower.

    public int shortestPathInSmallGraph(int[][] graph) {
        if (graph.length == 1) {
            return 0;
        }
        Set<Integer>[] adj = new HashSet[graph.length];
        int n = graph.length;
        int endState = (1 << n) - 1;
        boolean[][] seen = new boolean[n][endState];
        Queue<int[]> queue = new ArrayDeque<>();
        
        for (int i = 0; i < n; i++) {
            queue.add(new int[] {i, 1 << i});
            seen[i][1 << i] = true;
        }
        int steps = 0;
        while (!queue.isEmpty()) {
            int count = queue.size();
            for (int i = 0; i < count; i++) {
                int[] pair = queue.poll();
                int node = pair[0];
                int state = pair[1];
                for (int neighbor : graph[node]) {
                    int nextState = state | (1 << neighbor);
                    if (nextState == endState) {
                        return 1 + steps;
                    }
                    
                    if (!seen[neighbor][nextState]) {
                        seen[neighbor][nextState] = true;
                        queue.add(new int[] {neighbor, nextState});
                    }
                }
            }
            steps++;
        }
        return -1;
    }

Upvotes: 2

AlexAlvarez
AlexAlvarez

Reputation: 829

You can reduce it to the normal Travelling Salesman Problem by transforming the graph.

First, compute the minimum distance for every pair of nodes. You can use Floyd-Warshall algorithm for that. Once you have it, just construct the complete graph where the edge between nodes u and v is the minimum cost from u to v.

Then, you can apply a normal TSP algorithm as you don't have to revisit nodes anymore, that's already hidden in the costs of the edges.

Upvotes: 5

Related Questions