На этом шаге рассмотрим задачу приводящую к графу с ребрами, имеющими отрицательный вес.
В предыдущем примере Саша предложил в обмен на книгу один из двух предметов (рис.1).
Рис.1. Предложения Саши для обмена
Предположим, Лиза предложила обменять пластинку на постер и при этом она еще и даст Васе 7 тыс.рублей. Вася ничего не тратит при этом обмене, вместо этого он получит 7 тыс.рублей. Как изобразить это предложение на графе? (рис.2)
Рис.2. Ребро с отрицательным весом
Ребро, ведущее от пластинки к постеру, имеет отрицательный вес! Если Вася пойдет на этот обмен, он получит 7 тыс. рублей. Теперь к постеру можно добраться двумя способами (рис.3).
Рис.3. Проход по графу
А значит, во втором обмене появляется смысл - Вася получает 2ты. рублей! Теперь Вама может обменять постер на барабан. И здесь возможны два пути (рис. 4).
Рис.4. Продолжение обмена
Второй путь обойдется на 2 тыс. рублей дешевле, следовательно, нужно выбрать его.
На следующем шаге рассмотрим что произойдет, если применить алгоритм Дейкстры к этому графу.
