Предположим, у меня есть граф G = (V, E), который содержит черные и зеленые ребра. Учитывая целое число n, я хочу найти путь, который содержит, по крайней мере, n зеленых ребер. (Начиная с любого узла). Он должен работать в O (n | V | + n | E |) * log (n | V)
Только время выполнения говорит мне, что я буду использовать какой-то модифицированный алгоритм Дейкстры. Я знаю, что эти проблемы обычно решаются созданием нескольких копий исходного графа G и объединением их в один граф G '. Здесь, я думаю, я бы взял все зеленые ребра в G1 и укажу их на соответствующую им вершину fun G2. Но это все равно не дает мне ни одного исходного узла для начала.