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

Ответ: 17

Чтобы определить длину кратчайшего пути между пунктами А и Е, нужно рассмотреть все возможные пути и выбрать самый короткий.

Из таблицы видно:

• Путь напрямую из A в E: 18
• Рассмотрим другие пути:
  • A -> Б -> E = 1 + 6 = 7
  • A -> В -> E = 5 + 6 = 11
  • A -> Б -> В -> E = 1 + 2 + 6 = 9
  • A -> Б -> Г -> E = 1 + X + 6

Из таблицы видно, что из пункта Б в пункт Г нет пути, а из пункта Г в пункт Е - 6. Самый короткий путь A -> Б -> Д -> E = 1 + X + 1 = X + 2

• A -> В -> Г -> Д -> E = 5 + 1 + 2 + 1 = 9
• A -> Б -> В -> Г -> Д -> E = 1 + 2 + 1 + 2 + 1 = 7

Давай проверим другой путь A -> Б -> В -> Г -> E, который невозможен, так как нет прямого пути из Г в E

Кратчайший путь A -> Б -> В -> Д -> E = 1 + 2 + 2 + 1 = 6

Однако, у нас есть еще путь A -> Б -> Д -> E, который невозможен, т.к. нет прямого пути между Б и Д

Путь A -> В -> Г -> Е также невозможен, т.к. нет прямого пути между Г и Е

Рассмотрим путь A -> Б -> Е

• A -> Б -> Е = 1 + X. Из условия, что есть путь из пункта Е до пункта Б, то значение X = 16
• A -> Б -> Е = 1 + 16 = 17

Ответ: 17