Сельская малокомплектная школа находится в поселке Ивановское. Коля Иванов живет в деревне Вершки. Определите, какое минимальное расстояние ему надо пройти, чтобы добраться до школы:
Борки | Вершки | Красное | Дальнее | Дубово | Ивановское
Борки | | 5 | 8 | 10 | | 9
Вершки | 5 | | | 4 | 2
Красное | 8 | | | | 1 | 3
Дальнее | 10 | 4 | | | | 5
Дубово | | 2 | 1
Ивановское | 9 | | 3 | 5
Борки | Вершки | Красное | Дальнее | Дубово | Ивановское
Борки | | 5 | 8 | 10 | | 9
Вершки | 5 | | | 4 | 2
Красное | 8 | | | | 1 | 3
Дальнее | 10 | 4 | | | | 5
Дубово | | 2 | 1
Ивановское | 9 | | 3 | 5
Подсказка 1. Перепиши таблицу в виде списка связей: кто с кем соединён и какой ценой.
Подсказка 2. Ищи кратчайший путь перебором от старта: отбрасывай ветки, уже длиннее найденного.
Подсказка 3. Проверь направление движения: путь туда и обратно может отличаться.
Разбор.
Решение.
Найдем все варианты маршрутов от деревни Вершки до поселка Ивановское и выберем самый короткий.
Из пункта Вершки(В) можно попасть в пункты Борки(Б), Дальнее(Да) и Дубово(Ду).
Из пункта Б можно попасть в пункты Красное(К), Да, Ивановское(И).
Из пункта К можно попасть в пункты Ду, И.
Из пункта Да можно попасть в пункт И.
В—Б—К—И: длина маршрута 16 км.
В—Б—Да—И: длина маршрута 20 км.
В—Б—И: длина маршрута 14 км.
В—Да—И: длина маршрута 9 км.
В—Ду—К—И: длина маршрута 6 км.
Самый короткий путь: В—Ду—К—И. Длина маршрута 6 км.
Ответ.
6