Дейкстра - хороший способ найти кратчайшие пути. В вашем случае вам также нужно быть осторожным, чтобы первая вершина на вашем пути была красной, и чтобы вы могли использовать синие вершины, только если вы посетили зеленую.
Решение может быть следующим (в питоническом псевдокоде):
def red__and_green_dijkstra(G, origin, dest):
for node in G.nodes():
node.was_visited_R = False
node.was_visited_RG = False
origin.was_visited_R = True
origin.was_visited_RG = True
Q = empty_priority_queue()
for neighbor in origin.neighbors():
if neighbor.color == red:
Q.push((weight(origin, neighbor), neighbor, [origin, neighbor], False))
if neighbor.color == green and origin.color == red:
Q.push((weight(origin, neighbor), neighbor, [origin, neighbor], True))
while not Q.is_empty():
dist, node, path, can_pick_blue = Q.pop()
node.was_visited_R = True # mark the node as visited with a 'red' path
if can_pick_blue:
node.was_visited_RG = True # mark the node as visited on a 'red and green' path
if node == dest:
return path
for neighbor in node.neighbors():
if can_pick_blue: # met at least 1 green node on path so far
if neighbor.color == red and not neighbor.was_visited_RG:
Q.push(dist + (weight(node, neighbor), neighbor, path + [neighbor], True))
if neighbor.color == green and not neighbor.was_visited_RG:
Q.push(dist + (weight(node, neighbor), neighbor, path + [neighbor], True))
if neighbor.color == blue and not neighbor.was_visited_RG:
Q.push(dist + (weight(node, neighbor), neighbor, path + [neighbor], True))
else: # only red nodes on path so far
if neighbor.color == red and not neighbor.was_visited_RG:
Q.push(dist + (weight(node, neighbor), neighbor, path + [neighbor], False))
if neighbor.color == green and not neighbor.was_visited_RG:
Q.push(dist + (weight(node, neighbor), neighbor, path + [neighbor], True))
- Расстояние до источника: мы также используем его в качестве значения, по которому приоритет отдается в очереди (мы
pop() узлы с наименьшими расстояниями)
- текущий узел
- весь путь: поскольку вам нужен путь (а не только расстояние), вам также необходимо сохранить его в своей очереди
- логическое значение
can_pick_blue. Поскольку очередь была инициализирована красными узлами, мы уверены, что можем выбрать зеленый узел. Но для синих узлов мы должны быть уверены, что в пути есть хотя бы один зеленый и один красный узел. Это логическое значение отслеживает эту информацию. Можно было бы проверить все узлы на пути, но это было бы дороже.
Для инициализации нам нужно выделить 2 случая:
- если источник красного цвета, мы можем начать использовать красные и зеленые узлы, поскольку в пути уже есть красный узел.
- Если источник не красный, то мы должны выбрать красный узел.
Позже, когда мы зациклимся на соседях узла в основном цикле, нам нужно посмотреть, сможем ли мы поместить этого соседа в очередь. Поэтому мы должны проверить, что он еще не был посещен, и, в случае, если он синий, мы должны убедиться, что значение can_pick_blue для текущего узла действительно истинно.
Сложность этого алгоритма такая же, как и у Дейкстры, O(n.log n).
Редактировать : Чтобы получить правильные результаты, я добавил второе логическое значение, чтобы пометить узел как посещенный. В самом деле, вам нужно два из них: один, чтобы узнать, был ли узел посещен на пути «только красный», где выбор синего цвета запрещен, и один, чтобы узнать, был ли узел посещен на «красном и зеленом» (и в конечном итоге синий) путь, по которому также можно выбрать синие узлы.
Фактически требуется иметь возможность выбирать все соответствующие пути и отбрасывать лишние.