Полный граф только с двумя возможными затратами. Какова стоимость кратчайшего пути от 0 до N - 1

Это кропотливая работа над делом:

1. A ‹ B и 0 и N-1 соединены A -> тривиальным.
2. B ‹ A и 0 и N-1 соединены B -> тривиальным.
3. B ‹ A и 0 и N-1 соединены A -> Do BFS на графе только с K ребрами.

4. A ‹ B и 0 и N-1 соединены B -> Вы можете проверить за время O (N), существует ли путь длиной 2 * A (попробуйте каждую вершину в середине).

   Чтобы проверить другие длины пути, следующий алгоритм должен помочь: пусть X (d) будет набором узлов, достижимых с использованием d более коротких ребер из 0. Вы можете найти X (d), используя следующий алгоритм: Возьмите каждую вершину v с неизвестным расстоянием и итеративно проверить ребра между v и вершинами из X(d-1). Если вы нашли короткое ребро, то v находится в X(d), иначе вы наступили на длинное ребро. Так как существует не более K длинных ребер, вы можете наступить на них не более K раз. Таким образом, вы должны найти расстояние до каждой вершины не более чем за время O(N + K).

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

Вы можете использовать дерево сегментов, чтобы сделать работу Дейкстры более эффективной. Вам понадобятся операции

• установить верхнюю границу в диапазоне, как в заданных U, L, R; для всех x[i] с L ‹= i ‹= R, установите x[i] = min(x[i], u)
• найти глобальный минимум

Верхние границы можно лениво сдвигать вниз по дереву, поэтому оба варианта можно реализовать за O(log n)

При ослаблении исходящих ребер ищите ребра со стоимостью B, сортируйте их и обновляйте диапазоны между ними сразу.

Время выполнения должно быть O (n log n + m log m), если вы отсортируете все ребра заранее (по исходящей вершине).

EDIT: этот подход был принят. Хорошая вещь об этом заключается в том, что он избегает каких-либо специальных корпусов. Это все еще ~80 строк кода.

В случае, когда A ‹ B, я бы использовал своего рода BFS, где вы бы проверяли, куда вы не можете добраться, а не туда, где вы можете. Вот псевдокод:

G(k) is the set of nodes reachable by k cheap edges and no less. We start with G(0) = {v0}

while G(k) isn't empty and G(k) doesn't contain vN-1 and k*A < B
  A = array[N] of zeroes
  for every node n in G(k)
    for every expensive edge (n,m)
      A[m]++
  # now we have that A[m] == |G(k)| iff m can't be reached by a cheap edge from any of G(k)
  set G(k+1) to {m; A[m] < |G(k)|} except {n; n is in G(0),...G(k)}
  k++

Таким образом, вы избегаете повторения (много) дешевых ребер и перебираете только относительно небольшое количество дорогих ребер.

Как вы правильно заметили, проблема возникает, когда A > B и ребро от 0 до n-1 имеет стоимость A.

В этом случае вы можете просто удалить в графе все ребра со стоимостью A. Это потому, что оптимальный маршрут должен иметь только ребра со стоимостью B.

Затем вы можете выполнить простую BFS, поскольку стоимость всех ребер одинакова. Это даст вам оптимальную производительность, как указано в этой ссылке: Поиск кратчайшего пути для равных взвешенный график

Более того, вы можете остановить свой BFS, когда общая стоимость превысит A.