Я столкнулся с довольно сложной проблемой, которую сейчас пытаюсь объяснить с помощью некоторых изображений.
У меня есть сетевой график, который состоит из производителей и потребителей . Производители генерируют ресурсов , которые необходимо каким-то образом доставить потребителям.
Вот пример графика:
График является двунаправленным. Там может быть несколько производителей, а также потребителей.
Кроме того, существует несколько типов ресурсов . Например, один производитель может производить синие ресурсы, а другой - зеленые.
Для простоты предположим, что сначала существует только один вид ресурса, а расстояние между каждым узлом одинаковое.
Чтобы пояснить, что я ищу, я опишу текущий алгоритм, который более или менее прост.
Для каждого производителя (сейчас только один, но их может быть несколько), я вычисляю расстояние каждого узла до этого производителя (более или менее dijkstra):
Чтобы найти пути к производителю, я просто прохожу путь назад для каждого потребителя, всегда идя к узлу, который ближе к производителю.
График с большим количеством производителей и типов ресурсов может выглядеть следующим образом:
Поскольку это все еще слишком просто, давайте представим некоторые дополнительные расширения:
Узлы имеют скорость транспортировки. Это можно смоделировать, назначив веса краям. Так что это взвешенный график . Не большая проблема с текущим алгоритмом.
Существует множество производителей и потребителей, около 3000 производителей, 5000 потребителей и около 20 различных типов ресурсов.
Проблема , с которой я столкнулся:
Сейчас алгоритм плохо масштабируется для большего количества узлов. Если я добавлю новый узел, мне придется пересчитать всю сеть для каждого связанного ресурса, поскольку теперь могут быть более быстрые способы доставки ресурсов.
Я пытаюсь улучшить это, чтобы оно лучше масштабировалось до огромных графиков, поэтому я ищу более быстрый алгоритм .
Для справки, текущий код можно найти здесь .