Грокаем а Иллюстрированное пособие для программистов и любопытствующих

ЦИКЛ»



амо понятие ненаправленного графа означает, что каждый из двух узлов фактически ведет к другому узлу. А это цикл!
В ненаправленном графе каждое новое ребро добавляет еще один цикл. Ал­горитм Дейкстры работает только с направленными ациклическими графами, которые нередко обозначаются сокращением DAG (Directed Acyclic Graph).
История одного обмена
Н
о довольно терминологии, пора рассмотреть кон­кретный пример! Это Рама. Он хочет выменять свою книгу по музыке на пианино.
«Я тебе дам за книгу вот этот постер, — говорит Алекс. — Это моя любимая группа Destroyer. Или могу дать за книгу редкую пластинку Рика Эстли и еще $5». — «О, я слышала, что на этой пластинке есть отличные песни, — говорит Эми. — Готова отдать за постер или пластинку мою гитару или ударную установку».
« Всю жизнь мечтал играть на гитаре, — восклицает Бетховен. — Слушай, я отдам тебе свое пианино за любую из вещей Эми».
П
рекрасно! Рама с небольшими дополнительными тратами может поменять свою книгу на насто­ящее пианино. Теперь остается понять, как ему потратить наименьшую сумму на цепочке обменов. Изо­бразим полученные им предложения в виде графа:
Узлы графа — это предметы, на которые может поменяться Рама. Веса ребер представляют сумму доплаты за обмен. Таким образом, Рама может поменять постер на гитару за $30 или же поменять пластинку на гитару
за $15. Как Раме вычислить путь от книги до пианино, при котором он потратит наименьшую сумму? На помощь приходит алгоритм Дейкстры! Вспомните, что алгоритм Дейкстры состоит из четырех шагов. В этом при­мере мы выполним все четыре шага, а в конце будет вычислен итоговый путь.

1 ПЛАСТИНКА	5
1 ПОСТЕР	/*
[гитара	ОО 1
[барабан	ОО }
/ ПИАНИНО	Оо 1

МЫ ЕЩЕ НЕ ДОХОДИЛИ ДО ЭТИХ УЗЛОВ ОТ НАЧАЛЬНОГО


УЗЕЛ СТОИМОСТЬ

Прежде чем начинать, необходимо немного подготовиться. Постройте та­блицу со стоимостями всех узлов. (Стоимость узла определяет затраты на его достижение.)

Таблица будет обновляться по мере работы алгоритма. Для вычисления итогового пути в таблицу также необходимо добавить столбец «родитель».

УЗЕЛ	РОДИТЕЛЬ
ПЛАСТИНКА	КНИГА
ПОСТЕР	КНИГА
ГИТАРА	—-
БАРАБАН	•
ПИАНИНО	—

Вскоре я покажу, как работает этот столбец. А пока просто запустим алго­ритм.

Шаг 1: найти узел с наименьшей стоимостью. В данном случае самый де­шевый вариант обмена с доплатой $0 — это постер. Возможно ли получить постер с меньшими затратами? Это очень важный момент, хорошенько по­думайте над ним. Удастся ли вам найти серию обменов, при которой Рама
п