Намиране на път с минимален брой червени върхове в графика

Нека 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 -> b -> c -> t

person oronlaor    schedule 08.09.2015