|
Задание 1 |
Задание
3
Пример.
Между населёнными пунктами A, B, C, D, E,
F построены дороги, протяжённость которых (в
километрах) приведена в таблице:
Определить длину кратчайшего
расстояния между пунктами A и
F. Передвигаться можно только по дорогам, указанным в
таблице.
1) 9 2) 13
3) 14 4) 15.
Решение.
На основании таблицы строим граф. Из пункта А можно
попасть в пункты В, С и F, а из
них - в С,
D, E и т.д. Не забываем, что
стремимся именно в пункт F
(некоторые варианты можем не рассматривать, т.к. дорога до
пункта F по ним будет однозначно
длинной). Затем посчитаем длину пути по каждому маршруту и
выберем наименьший из них.
Ответ. 13.
|
