На этом шаге рассмотрим один из примеров поиска кратчайшего пути в графе.
Постановка задачи: Вася хочет выменять свою книгу по музыке на пианино.
"Я тебе дам за книгу вот этот постер, - говорит Саша. - Это мой любимый фильм. Или могу дать за книгу редкую пластинку и еще 5 тыс. рублей".
"0, я слышала, что на этой пластинке есть отличные песни, - говорит Лиза. - Готова отдать за постер или пластинку мою гитару или барабан".
"Всегда мечтал играть на гитаре, - говорит Миша. - Отдам пианино за любую из вещей Лизы."
Вася с небольшими дополнительными тратами может поменять свою книгу на настоящее пианино. Теперь остается понять, как ему потратить наименьшую сумму на цепочке обменов. Изобразим полученные им предложения в виде графа (рис.1):
Рис.1. Граф обменов
Узлы графа - это предметы, на которые может поменяться Вася. Веса ребер представляют сумму доплаты за обмен. Таким образом, Вася может поменять постер на гитару за 30 тыс. рублей или же поменять пластинку на гитару за 15 тыс. рублей. Как Васе вычислить путь от книги до пианино, при котором он потратит наименьшую сумму? На помощь приходит алгоритм Дейкстры!
Вспомните, что алгоритм Дейкстры состоит из четырех шагов. В этом примере мы выполним все четыре шага, а в конце будет вычислен итоговый путь.
Прежде чем начинать, необходимо немного подготовиться . Постройте таблицу со стоимостями всех узлов (рис. 2). Стоимость узла определяет затраты на его достижение.
Рис.2. Таблица
Таблица будет обновляться по мере работы алгоритма. Для вычисления итогового пути в таблицу также необходимо добавить столбец "родитель" (рис.3).
Рис.3. Столбец "родитель"
На следующем шаге рассмотрим первый шаг работы алгоритма Дейкстры.
