Как я могу найти самый дешевый способ в DAG, если у меня ограниченные деньги?

Эта задача относится к категории сложной NP, с сокращением от задача о рюкзаке.

Короткое интуитивное «доказательство»: идея в том, чтобы создать вершину для каждого элемента — вы можете «брать» или «не брать», выбирая вершину со стоимостью или «свободную» вершину. .

Эскиз:

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

Более формально:

Для экземпляра рюкзака с weights=w1,w2,w3,...cn и cost=c1,c2,..,cn с некоторым максимальным весом W создайте граф G=(V,E) с

V= { V_i,U_i,W_i | i=0,...n }
E= { (W_i,V_i+1,U_i+1 | i=0,...,n-1} U {(V_i,W_i+1), (U_i,W_i+1) | i=0,...,n-1 }

value(W_i,V_i+1) = c_i+1
money(W_i,V_i+1) = w_i+1
value(W_i,U_i+1) = 0
money(W_i,U_i+1) = 0
money(V_i,W_i+1) = cost(V_i,W_i+1) = money(U_i,W_i+1) = cost(U_i,W_i+1) = 0

Решение этой задачи, которое использует не более W денег, будет также решением для рюкзака с максимальной вместимостью W.

Возможным псевдополиномиальным решением может быть (с использованием метода динамического программирования) :

D(start,0) = 0
D(v,x) = infinity     x < 0
D(v,x) = min { D(u,x-money(u,v)) + value(u,v) | for each edge (u,v) } U {infinity}

В приведенном выше D(v,x) минимальное расстояние, необходимое для путешествия от начального узла до v, заплатив ровно x денег.

Обратите внимание, что это можно сделать, потому что это DAG, поэтому вы можете вычислять значения от первого до последнего в соответствии с топологическая сортировка.

Когда закончите, вам нужно найти все значения x от 0 до MAXIMAL_AMOUNT_OF_MONEY_ALLOWED, чтобы найти минимальное значение D(target,x), и это ответ.
Нахождение фактической стоимости выполняется путем повторного отслеживания ваших шагов, как это делается в других решениях динамического программирования.

Вышеуказанная продолжительность работы O(|V|*MAX_MONEY + |E|)

Используйте алгоритм флуда. Правила:
В каждом посещенном узле обновить массив путей и их цен.
Освободить массив, когда посещенный узел больше не нужен.
Всегда удалять пути с ценой > денег.
Начать флуд в на исходном узле.
Завершить наводнение в целевом узле, когда все входящие ребра будут заполнены.
Следовать за наводнением, используя исходящие ребра, когда все входящие ребра будут заполнены.
В конце выберите путь с самой высокой ценой в целевом узле. узел.

Поскольку ваш вопрос не о поиске пути вообще, а только о поиске пути в рамках определенной стоимости, я предполагаю, что у вас уже есть какой-то алгоритм поиска кратчайшего пути, и расскажу в целом о том, как его модифицировать.

Самый простой способ - просто игнорировать пути, которые увеличивают стоимость сверх суммы, которую вы хотите потратить. В вашем алгоритме поиска пути, когда вы добавляете ребро к пути, отказывайтесь от этого пути, если суммарная стоимость теперь слишком высока. Если разумно просто пропустить его или пометить как-то недействительным в вашем коде, сделайте это, иначе вы могли бы рассматривать вес суммы для пути как бесконечность, тогда он справится сам.

Предполагая, что у вас есть какая-то функция для проверки следующего ребра на пути (и если у вас ее нет или нет в этом формате, просто адаптируйте ее к тому, что у вас есть)...

// accepts the edge you are checking, max cost, and the sum weight and cost so far to this point
// returns float array {sum cost, sum weight), or infinity if cost is exceeded
void checkNextStep(Edge* edge, float maxCost, float* sumWeight, float* sumCost)
{
    if(*sumCost + edge->cost > maxCost)
    {
        *sumWeight = INFINITY;
        *sumCost += edge->cost;
    }
    *sumWeight += edge->weight;
    *sumCost += edge->cost;
}

Теперь этот путь будет автоматически отклонен, если стоимость превысит ваш порог, потому что бесконечность, скорее всего, не будет кратчайшим путем.

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