Алгоритм, который вы ищете, называется Алгоритм Флойда-Варшалла , очень хороший и эффективный алгоритм динамического программирования.Он может использоваться для вычисления набора узлов, достижимых для каждого отдельного узла в графике ( транзитивное замыкание ), хотя чаще используется для вычисления кратчайших путей из каждого отдельного узлана графике ко всем остальным узлам.
(Правка: алгоритм Флойд-Варшалла сложнее, чем нужно для вашего использования, поскольку он был немного расширен Флойдом для вычисления кратчайших путей. Вы можете найти эта страница полезная, которая описывает только часть "Warshall" алгоритма - ту часть, которая вам нужна.)
Я изучаю ее прямо сейчас для класса, и у меня есть статья на моемстол письменный.Рецидив для версии FW с транзитивным замыканием:
T(i,j,k) = T(i,j,k-1) ∨ (T(i,k,k-1) ∧ T(k,j,k-1))
Где T(a,b,c) истинно тогда и только тогда, когда существует путь от a до b с использованием только первых вершин c в графе (вы должныдайте им произвольную нумерацию перед запуском алгоритма).
Интуитивно, рекуррентность говорит, что есть путь от i до j с использованием первых k вершин, если:
- есть прямой путьмежду i и j, используя первые k-1 вершины, ИЛИ
- есть путь между i и k и путь между k и j, используя первые k-1 вершины.
Вы можете построить всю трехмерную таблицу T (i, j, k) типичным способом динамического программирования, а затем сосчитать все ИСТИННЫЕ записи по желаемому исходному узлу (используя max k), чтобы получить размер транзитивного замыкания для этого исходного узла.
Если вы все еще следуете моему плохому объяснению, вы можете сделать алгоритм чрезвычайно эффективным с помощью нескольких приемов:
Это туВыяснилось, что вам не нужно измерение k в вашей таблице;Вы можете просто перезаписывать один и тот же ряд значений снова и снова.Теперь программа будет выглядеть так:
T(i,j) = T(i,j) || (T(i,k) && T(k,j))
Если T (i, k) равно 0, то вы можете пропустить все это, так как ничего не изменится на этомstep.
- Если T (i, k) равно 1, то новым значением будет просто
T(i,j) || T(k,j).Это может быть сделано большими кусками, потому что блок OR очень быстро работает на современных процессорах.
Надеюсь, это поможет ...