На графике, как рассчитать сумму всех узлов, которые узел может эффективно достичь?

Question

С учетом ориентированного графа с весом, назначенным каждому узлу.
Начните с любого узла A, будет набор узлов, которые могут быть достигнуты из A.
Определите СУММУ как общий вес этого набора.

Вопрос: Как эффективно рассчитать SUM для каждого узла в этом графе?
Граф может содержать миллионы узлов.

Обновление 1:
Структура данных графа состоит из набора начальных узлов, и каждый узел имеет набор узловых точек.

Что я пробовал:
Вычислить потомков каждого узла рекурсивно и вычислить SUM в соответствии с набором потомков. Эта рекурсия очень неэффективна, так как мне приходится многократно выполнять операцию объединения, изменения. Далее я попытался кэшировать набор потомков на каждом узле. Тем не менее, он легко исчерпывает память.
Итак, есть ли другое решение?

Обновление 2:
Пример графа, все ребра направлены, верхние узлы указывают на нижние узлы

Результат должен быть
СУММА (1) = 55 СУММА (2) = 35 СУММА (3) = 41 СУММА (4) = 19 СУММА (5) = 22 СУММА (6) = 25 ...

Answer 1

Найти SCC для графа (алгоритм Тарьяна или двойной запуск DFS).

Для каждого SCC вычислите сумму весов его узлов, обозначьте это значение PARTIAL-SUM.

Итерация по SCC в обратном топологическом порядке; для каждого узла в каждом SCC его SUM будет суммой всех значений SUM смежных SCC плюс его собственное значение PARTIAL-SUM.

Линейное время работы O(E+V), поскольку обнаружение SCC является линейным, топологическая сортировка линейной, а суммирование линейным, поскольку мы посещаем каждый SCC не более одного раза и каждую ветвь не более одного раза.

EDIT

Как было отмечено в комментариях, tzkuzzy параллельные пути создают проблему. Это легко решается простым запуском DFS на графике SCC. На любом перекрестке мы просто берем уже посещенный узел вверх по дереву DFS, пока не достигнем не полностью искомого родителя, у этой пары узлов (посещенный снизу и предок) есть два разных пути между ними, мы составьте список для каждого узла таких потомков, а при суммировании просто вычтите их значение PARTIAL-SUM.

Так что если:

 u
/ \
\ /
 w

Наша DFS выберет перекрестную границу, соединяющую дочерний узел с u до w, и проследит до u (для тех, кто знаком с типичной DFS, изучаемой в школах, самое простое объяснение состоит в том, что u характеризуется как первый серый предок w), поэтому мы добавляем w в список, который мы поддерживаем u.

Затем, когда мы суммируем соседние SCC каждого SCC, как описано, мы добавляем дополнительный шаг, где мы перебираем упомянутый список и просто вычитаем значения PARTIAL-SUM.

Сам DFS все еще линейный. Откат от узла к предку может быть линейным, если мы кешируем результаты (таким образом, мы не пересекаем одно и то же ребро более одного раза). И дополнительная работа при суммировании составляет самое большее O(V), поэтому мы не изменили время выполнения.

EDIT

Включение-исключение делает это более трудным, чем я сначала думал. Это решение не является полным и не работает. Простая BFS для каждого узла дороже, но проще и будет работать.

Answer 2

Мой предыдущий ответ - хорошая идея, но включение-исключение пересекающихся поддеревьев очень трудно решить (я думаю, что ваш рекурсивный подход также пострадает).Если подумать, я начинаю сомневаться в том, существует ли хотя бы такая подструктура оптимальности в этой задаче, которая могла бы дать решение для динамического программирования ...

Я предложу гораздо более простую (хотя и менее эффективную)) решение:

Для каждого узла запустите BFS / DFS и суммируйте значения всех найденных узлов.Он будет работать в O(V) пространстве и O(V(E+V)) = O(EV) времени, но супер прост в реализации и не должен быть рекурсивным.

Вы можете оптимизировать, найдя график SCCи вместо выполнения BFS / DFS на каждом узле, сделайте это один раз для каждого SCC.Это может значительно увеличить время выполнения, если график «кликай».