Контрольные задания > Использование графов при решении задач Задача 1 Между населёнными пунктами А, В, С, D, Е построены дороги, протяжённость которых (в километрах) приведена в таблице. Определите длину кратчайшего пути между пунктами А и D. Передвигаться можно только по дорогам, протяжённость которых указана в таблице. Каждый пункт можно посетить только один раз.
Вопрос:

Использование графов при решении задач Задача 1 Между населёнными пунктами А, В, С, D, Е построены дороги, протяжённость которых (в километрах) приведена в таблице. Определите длину кратчайшего пути между пунктами А и D. Передвигаться можно только по дорогам, протяжённость которых указана в таблице. Каждый пункт можно посетить только один раз.

Ответ:

  1. Путь A-B-C-D: 2 + 1 + 4 = 7 км.
  2. Путь A-C-D: 4 + 4 = 8 км.
  3. Путь A-E-D: 5 + 3 = 8 км.
  4. Путь A-B-E-D: 2 + 1 + 3 = 6 км.
  5. Путь A-C-E-D: 4 + 1 + 3 = 8 км.
  6. Путь A-B-C-E-D: 2 + 1 + 1 + 3 = 7 км.
Кратчайший путь между пунктами А и D равен 6 км.
Смотреть решения всех заданий с листа