Есть ли лучший способ, чем алгоритм Дейкстры, найти быстрый путь, который не превышает указанную стоимость

Question

У меня проблема с поиском быстрого пути, который не превышает указанную стоимость. Есть схожий вопрос с этим, однако между ними есть большая разница. Здесь единственными записями, которые могут появиться в данных, являются те, которые ведут от нижней точки к более высокой точке (например, 1 -> 3 может появиться, но 3 -> 1 может не появиться) (см. Ниже). Не зная этого, я бы использовал Дейкстру. Эта дополнительная информация может позволить сделать это быстрее, чем алгоритм Дейкстры. Что вы думаете об этом?

Допустим, у меня указана максимальная стоимость и 4 записи.

// specified cost
    10 
// end point
    5
//(start point) (finish point) (time) (cost)
    2 5 50 5
    3 5 20 9
    1 2 30 5
    1 3 30 7
// all the records lead from a lower to a higher point no.

Я должен решить, возможно ли добраться из пункта (1) в (5) (это невозможно, когда нет пути, который стоит <=, чем у нас, или когда нет связи между 1-5) и если да, то что был бы самый быстрый способ попасть туда.

Выход для таких данных будет:

80 // fastest time
3 1 // number of points that (1 -> 2)  -> (2 -> 5)

Имейте в виду, что если есть запись о том, что вы можете двигаться 1->2

1 2 30 5

Это не позволяет вам двигаться 2<-1.

Answer 1

Для каждого узла на глубине n минимальная стоимость пути к нему равна n/2 * (minimal first edge at the path + minimal edge connecting to the node) - сумма арифметических рядов. Если это вычисление превышает требуемый максимум, нет необходимости проверять следующие узлы. Отрежьте эти узлы и примените Дейкстру к остальным.