Search code examples
algorithmpath-finding

Efficient way of getting all possible paths + special detail

I'm facing a path finding problem in which I have to find every possible path from one point to another. It would be very easy if it was just that - I'd use a breadth-first algorithm, just like the one explained here.

The problem is that, in this case, every edge has a maximum number of times that can be used. Let's see it with an example:

Example graph

In this case, I can go 15 times from A to D. The first 10 times, the path would be A -> B -> C -> D. The remaining 5 times, the path would be A -> C -> D.

So far I've been able to implement a solution (using python) but it's quite slow for medium problems (about 30 nodes). I have an unweighted graph (as I don't mind the length of the path) with the possible connections between the different nodes, and separately I have a matrix with the usage limit of each edge.

So, inside a loop:

  • I find a single possible path.
  • I update the matrix of usages. The usage of that path would be the minimum of the usages of the edges (as in, you can use a path as many times as the part of the path with the minimum limit).
  • For each edge whose usage reaches 0, it means it can no longer be used, so I delete it from the graph.
  • Loop until all paths are found.

As I said, this works, but it's quite slow. I've been able to increase the overall performance by sorting the list of edges for each node based on the number of times it can use, but it's still slow.

Any clues?

Solution

  • You could present your problem as a maximum flow problem. Instead of saying that you can travel A to B 10 times, you might say A to B may accomodate a flow of 10 m^3/s. And your graph is a network of pipes that may accomodate a total flow of 15m^3/s from A to D. So you may start with a look at the algorithms listed here on wikipedia.

    There are some points that are unclear to me in your problem. Depending on your answer, it might not qualify as a flow problem.

    1. If you increase the A to C capacity to 6, the maximum flow from A to D is still 15, but there are several ways to realise that (either 6 directly to C and 9 through B or 5 and 10). Are you satisfied with any of these answers or do you want them all ? In the same spirit, if there were another path from A to C (say through a node E) would you accept it to be ignored in the results, as C to D is saturated anyway.
    2. If there were a cycle in a graph (say an edge from C back to B) would you count going through this cycle never, once, twice or more as different solutions.