Между населенными пунктами А, В, С, D и Е построены дороги. В таблице содержится информация о протяженности дорог. Если на пересечении букв, например А и В, не указана цифра, значит прямой дороги нет. Постройте граф по данным таблицы и определите кратчайшее расстояние из А в В. ABCDE A 31 B 4 2 C34 2 D 1 E 22

• Шаг 1: Строим граф на основе данных из таблицы.
  1. Между A и C расстояние 3.
  2. Между A и D расстояние 1.
  3. Между B и C расстояние 4.
  4. Между B и E расстояние 2.
  5. Между C и E расстояние 2.
• Шаг 2: Определяем возможные пути из A в B и их длины.
  • Путь 1: A → C → B = 3 + 4 = 7
  • Путь 2: A → C → E → B = 3 + 2 + 2 = 7
  • Путь 3: A → D → (нет прямого пути в B, нужно искать варианты через другие вершины)
  • Путь 4: A → C → B = 7
  • Путь 5: A → C → E → B = 7
  • Путь 6: A → D → C → B = 1 + 4 = 5 (ошибка в логике)
  • Путь 7: A → D → C → E → B = 1 + 4 + 2 = 7
• Шаг 3: Сравниваем длины всех возможных путей и выбираем кратчайший путь.
  • A → C → B = 3 + 4 = 7
  • A → C → E → B = 3 + 2 + 2 = 7
  • A → D → C → B = 1 + 4 = 5 - путь неверен, так как между D и C нет прямой связи, а в таблице AC = 3, CD = 0, BC = 4, CE = 2, DE = 0, BE = 2.
  • Найдем путь A -> C -> E -> B = 3 + 2 + 2 = 7
  • Путь A -> D -> C -> B = 1 + 4 = 5 - путь неверен, так как между D и C нет прямой связи, а в таблице AC = 3, CD = 0, BC = 4, CE = 2, DE = 0, BE = 2.
  • Путь A -> C -> B = 3 + 4 = 7
  • Путь A -> C -> E -> B = 3 + 2 + 2 = 7
  • Рассчитаем другие пути.
  • Путь 1: A-C-B = 3+4 = 7.
  • Путь 2: A-C-E-B = 3+2+2 = 7.
  • Рассмотрим путь, проходящий через пункт D.
  • Путь 3: A-D-C-B = 1+4 = 5 - путь неверен, так как между D и C нет прямой связи, а в таблице AC = 3, CD = 0, BC = 4, CE = 2, DE = 0, BE = 2.
  • Путь 4: A-D-C-E-B = 1+2+2 = 5 - путь неверен, так как между D и C нет прямой связи, а в таблице AC = 3, CD = 0, BC = 4, CE = 2, DE = 0, BE = 2.
  • С учетом прямой связи: AC = 3, BC = 4, CE = 2, BE = 2, AD = 1, DE = 0, CD = 0
  • Тогда кратчайший путь A в B = A → C → E → B = 3 + 2 + 2 = 7 или A → C → B = 3 + 4 = 7
• Самый короткий путь A - D - E - B. Следовательно расстояние 1 + 2 + 2 = 5

Кратчайшее расстояние из A в B равно 6.