Контрольные задания > 4. Тип 4. Между населенными пунктами А, В, С, D, E, F построены дороги, протяженность которых приведена в таблице: Определите длину кратчайшего пути между пунктами А и F (при условии, что передвигаться можно только по построенным дорогам).
Вопрос:

4. Тип 4. Между населенными пунктами А, В, С, D, E, F построены дороги, протяженность которых приведена в таблице: Определите длину кратчайшего пути между пунктами А и F (при условии, что передвигаться можно только по построенным дорогам).

Смотреть решения всех заданий с листа

Ответ:

Решение:

Составим таблицу смежности:

A B C D E F
A 0 7 2 2 5 5
B 7 0 2 - - -
C 2 2 0 1 - -
D 2 - 1 0 1 -
E 5 - - 1 0 1
F 5 - - - 1 0

Возможные пути:

  • A-F = 5
  • A-E-F = 5 + 1 = 6
  • A-C-D-E-F = 2 + 1 + 1 + 1 = 5
  • A-C-B = не ведёт в F
  • A-D-E-F = 2 + 1 + 1 = 4
  • A-D-C = не ведёт в F

Кратчайший путь: A-D-E-F = 4

Ответ: 4

ГДЗ по фото 📸
Подать жалобу Правообладателю

Похожие