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:

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?

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.