Подсчет количества кратчайших путей через узел в группе доступности базы данных

Question

Я ищу алгоритм для подсчета количества путей, пересекающих определенный узел в группе обеспечения доступности баз данных (аналогично понятию «промежуточность»), со следующими условиями и ограничениями:

Мне нужновыполнить подсчет для набора узлов источника / назначения в графе, а не для всех узлов, то есть для среднего узла n, я хочу знать, сколько различных кратчайших путей от множества узлов S до множества узлов D проходят через n (и под различными, я имею в виду каждые два пути, которые имеют хотя бы один не общий узел)

Какие алгоритмы вы можете предложить для этого, учитывая, что DAG может быть очень большим, но разреженным по краямследовательно, предпочтение не отдается глубоким вложенным циклам на узлах.

Answer 1

Вы можете использовать поиск в ширину для каждой пары узлов Src / Dest и посмотреть, какие из них имеют данный узел в пути. Вам придется немного изменить поиск, чтобы, найдя кратчайший путь, вы продолжали очищать очередь до тех пор, пока не достигнете пути, который заставит вас увеличить размер. Таким образом, вы не связаны случайной случайностью, если существует несколько кратчайших путей. Конечно, это только опция с невзвешенными графиками.