javascript - 用于许多节点的 Dijkstra / 性能改进

Question

我正面临一个相当困难的问题，我现在正试图借助一些图像来解释它。

我有一个由Producers和Consumers组成的网络图。生产者生成资源，这些资源需要以某种方式交付给消费者。

这是一个示例图：

该图是双向的。可以有多个生产者和消费者。此外，还有多种类型的 Resources。例如，一个生产者可以生产蓝色资源，而另一个生产者可以生产绿色资源。为方便起见，我们先假设只有一种资源，并且每个节点之间的距离相同。

为了更清楚我在寻找什么，我将描述当前的算法，它或多或少是简单的。

对于每个生产者（现在只有一个，但可能有多个），我计算每个节点到该生产者的距离（或多或少 dijkstra）：

为了找到生产者的路径，我简单地为每个消费者向后遍历路径，总是去一个离生产者更近的节点。

包含更多生产者和资源类型的图表可能如下所示：

因为这仍然太容易了，让我们介绍一些进一步的扩展：

1. 节点具有传输速度。这可以通过为边缘分配权重来建模。所以这是一个加权图。不过，目前的算法并不是什么大问题。

2. 生产者和消费者有很多，大约有 3000 个生产者，5000 个消费者，大约有 20 种不同类型的资源。

我面临的问题是：

目前，该算法不适用于更多节点。如果我添加一个新节点，我必须为每个相关资源重新计算整个网络，因为现在可以有更快的方法来交付资源。

我正在努力改进这一点，因此它可以更好地扩展到巨大的图表，这就是我正在寻找更快的 Algorithm的原因。

作为参考，可以在此处找到当前代码。

标签： javascriptperformancegraph-theorydijkstra