Как найти наименьшее значение, достижимое из узла в DAG за линейное время?

Я пытаюсь следовать 3.25(a) с http://seed.ucsd.edu/mediawiki/images/4/43/Sol3.pdf

Я понимаю, что сначала вам нужно выполнить топологическую сортировку на графике. Но я не понимаю, как они получают min в cost[w]. Если есть 2 исходящих ребра из u, как вы их учитываете, используя этот алгоритм?


graph algorithm depth-first-search topological-sort
person minionhacking    schedule 12.04.2015    source источник

Ответы (1)


arrow_upward
0
arrow_downward

По сути это динамическое программирование. При наличии нескольких исходящих узлов вы выбираете минимум на каждом этапе. Это дает общее значение min, когда вы, наконец, достигнете исходной точки. Нарисуйте пример и выполните его.

person Edward Doolittle    schedule 12.04.2015
comment
Итак, если у меня есть что-то вроде A = 4, B = 4, C = 5 и C‹--A--›B, где я начинаю с A, верхняя сортировка будет ‹A, C, B›. Таким образом, вы должны сделать стоимость [B], затем стоимость [C], затем стоимость [A]. Как вы выбираете минимум в A, это дополнительный обход? - person minionhacking; 12.04.2015
comment
Возможно, я неверно истолковал обратный топологический порядок. Если я начну с A, то я смогу пройти через него линейно. Это правильно? - person minionhacking; 12.04.2015
comment
Возьмем чуть более сложный пример: A -> B, A -> C, B -> D, C -> E, D -> E. A = 4, B = 4, C = 5, D = 2, E = 3. У нас есть дополнительная переменная x_n = min, достижимая из узла x, которая изначально не определена. Работая в обратном порядке по верхней сортировке, x_E = 3; x_D = мин (2, x_E) = мин (2,3) = 2; х_С = мин (5, х_Е) = мин (5,3) = 3; x_B = мин (4,x_D) = мин (4,2) = 2; наконец, x_A = min(4,x_B,x_C) = min(4,2,3) = 2. В качестве бонуса мы получаем путь к минимальному значению, снова работая вперед: просто следуйте двойкам. Если есть более одной ветви, ведущей к 2, это не имеет значения. - person Edward Doolittle; 12.04.2015
comment
Окей, это имеет смысл. Спасибо за вашу помощь! - person minionhacking; 12.04.2015