Все минимальные пути между вершинами графа

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).

Я думал о том, чтобы найти все пути длины ровно k, а затем проверить стоимость этих путей, чтобы увидеть, находится ли он в пределах границ. Однако я не уверен, как реализовать эту идею (возможно, с BFS илиdijkstra) и я тоже думаю, что это грубая сила, так что, возможно, есть более умная идея?

Answer 1

Прежде всего возьмите log для всех затрат на графике, поэтому при суммировании их будет похоже на умножение весов (начиная с log a + log b = log a * b).Тогда вы сможете использовать все известные вам алгоритмы.

Отсюда я вижу два решения:

1. Найти все пары кратчайших путей , затем возьмите от них только пути длиной k.Это займет O(V^3) для поиска путей.

2. Используйте этот вопрос для нахождения всех путей длины k.Вам нужно будет самостоятельно определить сложность времени.

После этого вы можете перебирать результаты и брать только те, у которых есть необходимая сумма.Это займет O(E)*O(V^2) длину каждого пути * количество путей.
Более логичным вариантом будет удаление путей, которые вам не нужны в процессе работы алгоритма.

Не забудьтевернуть исходную длину в конце.

Удачи.