Между населенными пунктами А, В, С, D, Е построены дороги, протяженность которых (в километрах) приведена в таблице

Между населенными пунктами А, В, С, D, Е построены дороги, протяженность которых (в километрах) приведена в таблице

Задача. Между населенными пунктами А, В, С, D, Е построены дороги, протяженность которых (в километрах) приведена в таблице.

A B C D E
A 14 7 17
B 14 2 6 2
C 2 5
D 7 6 5 4
E 17 2 4

Определите длину кратчайшего пути между пунктами А и Е, проходящего через пункт В. Передвигаться можно только по дорогам, протяженность которых указана в таблице. Каждый пункт можно посетить только один раз.

Решение

Для наглядности нарисуем пункты и отметим расстояния между ними.

Рисунок к задаче про дороги между A B C D E
Рисунок к задаче про дороги между A B C D E

Постарайтесь нарисовать расположение пунктов как можно более близко к реальному, то есть соблюсти соотношение между сторонами, то есть если расстояние 17 км, оно не должно быть на вашем рисунке меньше, чем 7 км.

Теперь, когда у нас есть наглядное расположение дорог и населенных пунктов, мы можем видеть, что из А в Е через пункт B  можно пройти следующим путем:

  1. A ->B -> E
  2. A -> D -> B -> E
  3. A -> D -> C -> B -> E

Теперь подсчитаем каждый путь:

  1. A -> B -> E это 14+2=16 км
  2. A->D -> E это будет 7+6+2=15 км
  3. A ->D -> C -> B -> E это 7+5+2+2=16 км.

Значит, второй путь получается наиболее коротким и равен 15 км.

Ответ: 15.

Спасибо:
( Пока оценок нет )
Справочник для школьников
Подписаться
Уведомить о
0 комментариев
Межтекстовые Отзывы
Посмотреть все комментарии