Условие задачи
Некий человек N решил отправиться искать счастья в город М. В бюро путешествий ему показали карту Страны Р с нанесенными на ней автобусными маршрутами. Каждый круг на карте изображает населенный пункт. Для удобства они пронумерованы. Стоимость различных автобусных маршрутов различна (например, тем выше, чем длиннее путь). Обозначим через Cij стоимость проезда из пункта i в пункт j. Условные численные обозначения представлены на рис. 3.4. Найти оптимальный путь.
Ответ
Начинаем решать с конца: n = 1 первый шаг от города М (табл. 3.3).