Решение задачи: Кратчайший путь между пунктами A и E

Вот решение задачи, оформленное так, чтобы было удобно переписать в тетрадь школьнику: Задание 1 Между населёнными пунктами A, B, C, D, E построены дороги, протяжённость которых (в км) приведена в таблице. Определи длину кратчайшего пути между пунктами A и E. Передвигаться можно только по дорогам. Таблица дорог: | | A | B | C | D | E | |---|---|---|---|---|---| | A | | | 5 | 1 | | | B | | | 1 | 2 | 4 | | C | 5 | 1 | | 3 | 6 | | D | 1 | 2 | 3 | | 2 | | E | | 4 | 6 | 2 | | Решение: Для того чтобы найти кратчайший путь, мы будем последовательно рассматривать все возможные маршруты из пункта A в пункт E и выбирать самый короткий. 1. Начнём из пункта A. * Из A можно попасть в C (длина 5 км) и в D (длина 1 км). 2. Рассмотрим пути, начинающиеся с A-D: * A-D (1 км). Из D можно попасть в B (2 км), C (3 км), E (2 км). * A-D-E: \(1 + 2 = 3\) км. Это один из возможных путей. * A-D-B: \(1 + 2 = 3\) км. Из B можно попасть в C (1 км), E (4 км). * A-D-B-E: \(1 + 2 + 4 = 7\) км. * A-D-B-C: \(1 + 2 + 1 = 4\) км. Из C можно попасть в E (6 км). * A-D-B-C-E: \(1 + 2 + 1 + 6 = 10\) км. * A-D-C: \(1 + 3 = 4\) км. Из C можно попасть в B (1 км), E (6 км). * A-D-C-E: \(1 + 3 + 6 = 10\) км. * A-D-C-B: \(1 + 3 + 1 = 5\) км. Из B можно попасть в E (4 км). * A-D-C-B-E: \(1 + 3 + 1 + 4 = 9\) км. 3. Рассмотрим пути, начинающиеся с A-C: * A-C (5 км). Из C можно попасть в B (1 км), D (3 км), E (6 км). * A-C-E: \(5 + 6 = 11\) км. * A-C-B: \(5 + 1 = 6\) км. Из B можно попасть в D (2 км), E (4 км). * A-C-B-E: \(5 + 1 + 4 = 10\) км. * A-C-B-D: \(5 + 1 + 2 = 8\) км. Из D можно попасть в E (2 км). * A-C-B-D-E: \(5 + 1 + 2 + 2 = 10\) км. * A-C-D: \(5 + 3 = 8\) км. Из D можно попасть в B (2 км), E (2 км). * A-C-D-E: \(5 + 3 + 2 = 10\) км. * A-C-D-B: \(5 + 3 + 2 = 10\) км. Из B можно попасть в E (4 км). * A-C-D-B-E: \(5 + 3 + 2 + 4 = 14\) км. Соберём все найденные пути до E и их длины: * A-D-E: 3 км * A-D-B-E: 7 км * A-D-B-C-E: 10 км * A-D-C-E: 10 км * A-D-C-B-E: 9 км * A-C-E: 11 км * A-C-B-E: 10 км * A-C-B-D-E: 10 км * A-C-D-E: 10 км * A-C-D-B-E: 14 км Сравнивая все эти длины, видим, что кратчайший путь составляет 3 км. Ответ: 3