CODEWITHSUNDEEP
pythonnetworkxgraph-theory
JonLuca
JonLuca

Reputation: 919

Find shortest path in directed, weighted graph that visits every node with no restrictions on revisiting nodes and edges

I'm using the NetworkX Python library. A more extensive description of the problem I'm trying to solve is here.

I'd like to find both 1) a valid path that visits every node at least once and 2) the shortest path, based on edge weights, that visits every node at least once.

This sounds like a variation of the Travelling Salesman Problem. The other thing of note is that the graph is almost undirected - most of the nodes are bidirectionally connected, it's only a certain few (<20% of all nodes) that are unidirectionally connected.

I looked over the NetworkX algorithms but none seemed to satisfy this question.

The code used to generate the graph is:

    def generate_graph(self):
        ind = (12, 0)
        self.ball = ind
        locs = [ind]
        while len(locs):
            next_loc = locs.pop()
            if not self.nodes[next_loc]:
                self.nodes[next_loc] = AmazeGameLocation(next_loc)
                self.paths.add_node(self.nodes[next_loc])

            moves = [("U", (-1, 0)), ("D", (1, 0)), ("L", (0, -1)), ("R", (0, 1))]
            for move in moves:
                next_move_loc = add_tuples(move[1], next_loc)
                if self.is_move_possible(next_move_loc):
                    next_attempt = add_tuples(move[1], next_move_loc)
                    weight = 1
                    while self.is_move_possible(next_attempt):
                        next_move_loc = next_attempt
                        next_attempt = add_tuples(move[1], next_move_loc)
                        weight += 1
                    if not self.nodes[next_move_loc]:
                        self.nodes[next_move_loc] = AmazeGameLocation(next_move_loc)
                        self.paths.add_node(self.nodes[next_move_loc])
                        locs.append(next_move_loc)
                    self.paths.add_edge(self.nodes[next_loc], self.nodes[next_move_loc], weight=weight)
                    self.nodes[next_loc].dirs[move[0]] = self.nodes[next_move_loc]

A sample graph is here.

More information about this graph and issue is on my GitHub, here.

Upvotes: 1

Views: 661

Answers (1)

m.raynal
m.raynal

Reputation: 3123

I'd like to find both 1) a valid path that visits every node at least once and 2) the shortest path, based on edge weights, that visits every node at least once.

For 1): that's pretty simple, you can try to find for instance a spanning tree of your graph. You can then build a path that visits all vertices in your graph by traversing this spanning tree.

For 2): Let G be your graph, you can then build G' the 'metric completion' of G, meaning that the vertices of G' are the vertices of G, and for any couple of vertices u, v, there is an edge u,v in G', weighted with the weight of the shortest path from u to v in G.
Then all you have to do is solve a TSP on G' to obtain the solution you look for on G.

Upvotes: 0

Related Questions