Код презентации скопируйте его
Задача: На схеме нарисованы дороги между четырьмя населёнными пунктами А, В, С, Д и указаны протяжённости данных дорог: А С Д В 3 12 2 6
Задача: Определите. Какие 2 пункта наиболее удалены друг от друга (при условии, что передвигаться можно только по указанным на схеме дорогам). В ответе укажите кратчайшее расстояние между этими пунктами. 1) 11 2) 8 3) 12 4) 18
Решение: Запишем минимальное расстояние между всеми пунктами. При этом следует рассматривать все варианты маршрутов, в том числе через промежуточные пункты, чтобы выбрать из них минимальные.
Решение: 1) из А в В – 3 (самый короткий путь – напрямую); 2) Из А в С – 5 (короче будет проехать не по прямой дороге, а через пункт В); 3) из А в Д – 11 (с заездом в пункты В и С); 4) из В в С – 2;
Решение: 5) из В в Д – 8 (с заездом в пункт С); 6) из С в Д – 6. Наиболее удалённые пункты – А и Д, расстояние между ними составляет 11. Правильный ответ 1.
Решение: Вы можете занести все минимальные расстояния между пунктами в таблицу, в первой строке и первом столбце который запишем наименования пунктов. Всю таблицу заполнять не надо, так как кратчайший путь из пункта А в пункт В и из пункта В в пункт А совпадают.
Решение: Таким образом, достаточно заполнить правый верхний треугольник таблицы или левый нижний. Для заполнения таблицы необходимо из всех возможных путей между парами пунктов выбрать минимальный.