ОГЭ Информатика 2021: Краткий путь A-E

Разбор решения задачи на поиск кратчайшего пути между населенными пунктами.

Условие задачи

Между населенными пунктами A, B, C, D и E построены дороги. Протяженность дорог в километрах представлена в таблице:

От До Расстояние (км)
A B 5
A C 3
B C 1
B D 4
C D 6
D E 1

Необходимо определить длину кратчайшего пути между пунктами A и E, передвигаясь только по указанным дорогам.

Построение графа и поиск кратчайшего пути

Для решения задачи построим граф, где вершины – населенные пункты, а ребра – дороги с указанием их длины. Найдем кратчайший путь между A и E, рассматривая возможные маршруты:

  • Путь 1: A → B (5 км) → D (4 км) → E (1 км). Общая длина: 5 + 4 + 1 = 10 км.
  • Путь 2: A → C (3 км) → B (1 км) → D (4 км) → E (1 км). Общая длина: 3 + 1 + 4 + 1 = 9 км.
  • Путь 3: A → C (3 км) → D (6 км) → E (1 км). Общая длина: 3 + 6 + 1 = 10 км.

Результат

Кратчайший путь между пунктами A и E имеет длину 9 километров (A → C → B → D → E).

Задача решается построением графа и анализом возможных маршрутов. В данном случае, кратчайший путь найден путем полного перебора.

Что будем искать? Например,программа