Find all paths between two nodes using DFS in weighted directed graph

Question

I had a directed weighted graph G, where weight is duration of transition.

I wrote all paths search algorithm between two vertices using DFS with modification: the search continues until total weight of path (the sum of the weights of its parts) will be less some value.

My code works in small graph, but in big graph (|V|=1800, |E|=50870) it freezes.

def find_paths(self, start, end, weight_limit=10):
        res = []

        def dfs(start, end, path=[], weight=0):
            path = path + [start]
            if len(path) > 1:
                weight += self.weights[(path[-2], start)]
            if weight > weight_limit:
                return []
            if start == end:
                res.append((path, weight))
                return [path]
            if start not in self.adjacent:
                return []
            paths = []
            for node in self.adjacent[start]:
                if node not in path:
                    paths.extend(dfs(node, end, path, weight))
            return paths

        dfs(start, end)
        return res

Might be a memory error. Do you actually need to keep track of all the paths and their weights? — Jared Goguen
@JaredGoguen Yes I need to keep track of all the paths and their weights, because my goal is find ALL paths between START and END nodes in my GRAPH. So, if it is a memory error, is it possible solution to fix it? Any ideas? — Andrei
The total number of paths might grow factorially with the number of edges. Even 50! is too large to be approached by enumeration, never mind 50000!. — Jared Goguen
@JaredGoguen so, its impossible task to solve? I mean find all path between START and END in this graph with total_weight < certain value? — Andrei

Sorin Sorin · Accepted Answer · 2016-04-26T15:30:40

Your code seems correct (especially since it works on small graphs).

The problem is that there can be lots of paths between the nodes. For a fully connected graph the number of paths is on the order of N! which is a lot. Since you need all of them your program is going to be slow (especially if you run out of ram and need to swap things to disk).

If you limit the maximum total weight like you did in your code assuming all weights are one you still run in O(weight), which I assume you set to a large value since the graph is large.

You need to figure out if you really need all those paths.

If you are looking for the shortest path use Dijkstra or something for finding the shortest path.

Find all paths between two nodes using DFS in weighted directed graph

1 Answers