Все пути длины k из данной вершины

Question

Допустим, у меня есть ориентированный граф G (V, E) с реберной стоимостью (действительное число) ∈ (0,1). Для данного i мне нужно найти все пары вершин (i, j), начиная сi, которые "совпадают". Две вершины (i, j) совпадают, если существует направленный путь от i до j с длиной ровно k (k - заданное число, которое является относительно небольшим и может считаться постоянным) со стоимостью> = C(C - это заданное число). Стоимость пути рассчитывается как произведение его ребер. Например, если путь, начинающийся с i и заканчивающийся на j длины 2, состоит из ребер e1 и e2, тогда CostOfpath = cost (e1) * cost(e2).

Это должно быть сделано в O (E + V * k). Так что я думал об изменении алгоритма DFS, обновляющего расстояния от заданной начальной вершины i до тех пор, пока они не достигнут длины k.Если этого не произойдет, у нас не может быть совпадения. Но мне трудно найти, что именно я могу изменить в DFS. Есть идеи?

Answer 1

Когда вам нужно рассмотреть пути с фиксированным числом ребер, динамическое программирование часто приходит на помощь (в то время как другие подходы часто терпят неудачу).

Давайте обозначим dp[v][j] максимальную стоимость пути извершина i (фиксированная) к вершине v, которая имеет ровно j ребер.

Для начальных значений можно установить значения для j==1: dp[v][1] - это стоимость ребра от *От 1011 * до v (или 0, если такого ребра не существует).Или, если подумать, будет очевидно, что вы можете установить значения для j==0, а не j==1: dp[i][0] равно 1, тогда как dp[v][0] можно установить на ноль для v!=i.

Теперь, если у вас есть значения для некоторых j, легко вычислить значения для j+1:

dp[v][j+1] = max( dp[v'][j] * cost((v', v)) )

Это очень похоже на алгоритм Форд-Беллмана , толькочто последний не должен отслеживать количество ребер и, следовательно, может использовать одномерный массив.

Это дает решение в O((E+V)*k).Не совсем то, что вы просили, но я сомневаюсь, что существует решение в O(E+V*k).

(В приведенном выше решении я предполагаю, что константа C является положительной, и поэтому путь с нулевой стоимостью эквивалентенна пути, который абсолютно отсутствует. Если вам нужно, вы можете специально учесть случай C==0.