Ограниченное кратчайшее расстояние в графе

Question

Я столкнулся с этой проблемой на сайте кодирования, и я понятия не имею, как ее решить. Редакция недоступна, и я не смог найти ни одной связанной статьи в Интернете. Поэтому я спрашиваю это здесь.

Проблема:

У вас есть граф G, который содержит N вершин и M ребер. Вершины пронумерованы от 1 до N. Также каждый узел окрашен в черный или белый цвет. Вы хотите рассчитать кратчайший путь от 1 до N так, чтобы разница между черными и белыми узлами была не больше 1.

Как очевидно, применение прямого алгоритма Дейкстры не сработает. Любая помощь приветствуется. Спасибо!

Answer 1

Мы можем рассмотреть модифицированный граф и запустить Dijkstra на этом:

Для каждого узла в исходном графе модифицированный граф будет иметь несколько мета-вершин (теоретически, бесконечно много), каждая из которых соответствует разной черно-белой разнице. Вам нужно только создать узлы при изучении графа с Dijkstra. Таким образом, вам не нужно будет бесконечно много узлов.

Тогда края довольно просты (вы также можете создавать их во время исследования). Если вы в данный момент находитесь в узле с черно-белой разницей d, и исходный график имеет ребро для белого узла, то вы создаете ребро для соответствующего узла с черно-белой разницей d-1. Если исходный график имеет ребро для черного узла, вы создаете ребро в измененном графике для соответствующего узла с черно-белой разницей d+1. Вам не обязательно обрабатывать их как разные узлы. Вы также можете хранить переменные Дейкстры в узле, сгруппированном по черно-белой разнице.

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