Нахождение пути с минимальным количеством красных вершин в графе

Пусть G = (V, E) - неориентированный граф, s и t - две вершины в V. Каждое ребро графа окрашено в красный или синий цвет. Мне нужно найти алгоритм, который находит путь между s и t с минимальным количеством красных краев в нем.

Я подумал о следующем алгоритме: Модифицированный алгоритм BFS

Для каждой вершины мы будем использовать дополнительное поле, называемое «красный уровень», которое будет указывать минимальное количество красных ребер на пути от s до этой вершины. Как только мы обнаружим новую вершину, мы обновим ее красное поле уровня. Если мы пытаемся исследовать вершину, которая уже была обнаружена, если красный уровень этой вершины больше, чем текущий красный уровень, то мы удаляем эту вершину из дерева BFS и вставляем ее как дочернюю по отношению к вершине, дочерние элементы которой мы сейчас исследуем и так далее. Желаемый путь - это путь, соединяющий s и t в дереве BFS в конце выполнения алгоритма.

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


algorithm graph-theory language-agnostic
person Roy    schedule 14.03.2013    source источник

Ответы (2)


arrow_upward
6
arrow_downward

Я думаю, что это правильно: по сути, вы выполняете алгоритм Дейкстры с очень большими весами для красных краев. большой, а вес для синих краев очень мал или равен нулю.

person angelatlarge    schedule 14.03.2013
comment
Штопать! Вы меня опередили :-P Но я думаю, у вас все наоборот. Красные ребра имеют низкий вес, а синие ребра - высокие, так как он хочет найти путь красных ребер от S до T. - person Raymond Saltrelli; 15.03.2013
comment
Извините! Думаю, это означает, что если мы оба не идиоты, то этот ответ будет не более 0,5 тупым :) - person angelatlarge; 15.03.2013

arrow_upward
0
arrow_downward

К сожалению, алгоритм неверный. Возьмем следующий график: G = (V, E); V = {s, a, b, c, d, e, t}; E = {(s, a), [s, b], [s, d], (a, b), [b, c], [d, e], (c, t), (e, t) };

(Для удобства я пометил (,) для синего ненаправленного края и [,] для красного)

Предположим, алгоритм решает исследовать «b» перед «a». Когда мы закончим с «s», у нас будет «a» с уровнем красного 0, а «b» и «d» с уровнем красного 1. При исследовании с «d» у нас будет «e». с красным уровнем 2. Теперь исследуем от «b»: «s» и «a» остаются без изменений, но «c» получает красный уровень 2. Затем мы исследуем «a» (согласно BFS!), и это изменяет родительский элемент «b» на «a», а уровень красного для «b» становится равным 0. Обратите внимание, что в этой точке - путь от «s» к «c» правильный, но уровень красного на 'c' нет - он должен быть 1 вместо 2. Теперь мы продолжаем и извлекаем из 'e' (мы закончили с 's' и его непосредственными дочерними элементами 'a', 'b' и 'd'): мы обнаруживаем 't' с ребром (e, t), поэтому 't' получает красный уровень 2. Ребро (e, d) ничего не меняет. Теперь мы переходим к самой интересной части - исследованию от «c»: ребро (c, b) ничего не меняет, но как насчет ребра (c, t)? 't' уже обнаружен (от 'e'), поэтому в соответствии с вашим алгоритмом мы меняем что-то только в том случае, если есть разница в уровне красного. Но это не так, потому что уровень красного для буквы «c» равен 2 (неправильно!). Таким образом, родительский элемент 't' остается 'e', ​​а путь от 's' содержит 2 красных края, в то время как ЕСТЬ путь от 's' к 't', который содержит только 1 красное ребро: s -> a -> б -> в -> т

person oronlaor    schedule 08.09.2015