Контрольные задания > 4. Между населёнными пунктами А, В, С, D, E, F построены дороги, протяжённость которых приведена в таблице. Отсутствие числа в таблице означает, что прямой дороги между пунктами нет. Определите длину кратчайшего пути между пунктами А и F, не проходящего через пункт Е. Передвигаться можно только по указанным дорогам. ABCDEF A 748 16 B7 3 C4 3 D833 28 E 2 5 F 16 85
Вопрос:

4. Между населёнными пунктами А, В, С, D, E, F построены дороги, протяжённость которых приведена в таблице. Отсутствие числа в таблице означает, что прямой дороги между пунктами нет. Определите длину кратчайшего пути между пунктами А и F, не проходящего через пункт Е. Передвигаться можно только по указанным дорогам. ABCDEF A 748 16 B7 3 C4 3 D833 28 E 2 5 F 16 85

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

Ответ:

Тип задания – вычисление длины кратчайшего пути в графе, заданном таблицей.

Нужно найти кратчайший путь из пункта А в пункт F, избегая пункта E.

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

  1. A → B → D → F = 7 + 3 + 8 = 18
  2. A → C → D → F = 4 + 3 + 8 = 15
  3. A → D → F = 8 + 8 = 16
  4. A → F = 16

Кратчайший путь: A → C → D → F = 15

Ответ: 15

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