I'm facing a rather difficult problem which I'm now trying to explain with the help of some images.
I have a network graph which consists of Producers and Consumers. Producers generate Resources which need to somehow get delivered to the Consumers.
Here is an example graph:
The graph is bidirectional. There can be multiple producers as well as consumers. Additionally there are multiple types of Resources. For example, one Producer could produce blue resources, and another one could produce green ones. For the sake of easiness, lets assume there is only one kind of resource first, and the distance between every node is the same.
To make it more clear what I am looking for, I am going to describe the current algorithm, which is more or less simple.
For every producer (Right now only one, but there could be multiple), I compute the distance of every node to that producer (more or less dijkstra):
To find the paths to the producer, I simply traverse the path backwards for every consumer, always going to a node which is closer to the producer.
A graph with more producers and types of resources could look like this:
Because this is still way too easy, lets introduce some further extensions:
The nodes have a transport speed. This can be modelled by assigning weights to the edges. So this is a weighted graph. Not a big problem with the current algorithm though.
There are a lot of producers and consumers, approximately 3000 Producers, 5000 Consumers, and arround 20 different types of resources.
The problem I am facing is:
Right now the Algorithm scales bad for higher number of nodes. If I add a new node, I have to recalculate the whole network for every related Resource, since there could be now faster ways to deliver resources.
I am trying to improve this, so it scales better to huge graphs, which is why I am looking for a faster Algorithm.
For reference, the current code can be found here.