Конкретная проблема, которую вы описываете - поиск пути между двумя узлами, сводящий к минимуму количество используемых цветов, - NP -hard. Это означает, что, предполагая P ≠ NP , не существует алгоритма полиномиального времени для решения этой проблемы, и, в частности, алгоритм Дейкстры здесь не будет работать.
Вот сокращение, которое показывает это, которое основано на этом превосходном ответе Пола Хэнкина для связанной проблемы. Мы собираемся свести задачу о наборе ударов к проблеме поиска наименее красочного st-пути в графе. В задаче о ударе по множеству вы получаете набор множеств S 1 , ..., S n , содержащий всего m элементов и число k, затем спросите, Можно выбрать k элементов таким образом, чтобы каждый набор S i содержал хотя бы один из них.
Сокращение работает следующим образом. Мы собираемся построить график и раскрасить узлы одним из цветов m + 1. Первый цвет (назовем его черным) - это нейтральный цвет без значения. Оставшиеся m цветов будут соответствовать различным элементам из наборов.
Мы создадим цепочку «гаджетов», по одному на набор S i , которые соответствуют выбору некоторого элемента от S i . Вот как работает каждый гаджет:
- Каждый гаджет имеет начальный узел s i , окрашенный в черный цвет, и конечный узел f i , также окрашенный в черный цвет.
- Для каждого элемента x ∈ S i мы добавляем новый узел x i , учитывая цвет, связанный с элементом x. Затем мы добавляем ребро от s i до x i и от x i и t i .
Теперь представьте, как вы идете от s i до t i . Для этого нужно сделать два шага, посетив два черных узла (s i и t i ) и один узел другого цвета. Прогулка по этому цветному узлу соответствует выбору x i в качестве одного из элементов вашего ударного набора.
Чтобы завершить sh, соедините все гаджеты последовательно, связав f 1 с 2 , f 2 с 3 и др. c. Теперь посмотрите на любой путь от s 1 до f n . Если вы можете найти путь через график, который использует не более k + 1 цветов, один из этих цветов будет черным, а остальные k цветов соответствуют совокупности из k элементов, которые в совокупности содержат один элемент из каждого из наборов S я . Вы нашли свой ударный набор - отлично! С другой стороны, представьте, что у вас есть ударный набор размером k. Затем перейдите от s 1 к f n , делая выбор в каждой точке, в которой вам нужно выбрать цветной узел, соответствующий одному из предметов из набора ударов. Тогда вы будете использовать не более k + 1 цветов: черный плюс заданные цвета.
Этот график содержит 2n узлов для узлов s i и t i, плюс один узел для каждого элемента каждого набора с линейным числом ребер. Поэтому он имеет полиномиальный размер по отношению к экземпляру набора совпадений, так что это сокращение за полиномиальное время от попадания в вашу проблему.
Извините за (вероятно) отрицательный результат!