нарисовать график и решение

Краткий ответ: ВГ (4 км). Это прямая дорога между пунктами В и Г.

1. Граф по таблице

Таблица симметрична относительно диагонали: число в клетке на пересечении строки и столбца — длина дороги между этими пунктами. Пустая клетка — дороги нет. Выпишем все рёбра:

• А–Б = 3
• Б–Г = 1, Б–Д = 5, Б–Е = 1
• В–Г = 4, В–Д = 5
• Г–Д = 5, Г–Е = 3
• Д–Е = 6

Схема (числа — длины дорог):

              А
              │3
              Б
       1╱     │5     ╲1
       ╱      │       ╲
      Г       │        Е
     ╱ ╲      │       ╱
   4╱   ╲5    │    3 ╱
   ╱     ╲    │     ╱
  В       ╲   │    ╱
   ╲       ╲  │   ╱
    ╲ 5     ╲ │  ╱ 6
     ╲       Д╱

2. Решение

Из пункта В выходят всего две дороги: в Г (4 км) и в Д (5 км). Значит, любой путь В → Г начинается либо с шага ВГ, либо с шага ВД.

• Путь ВГ уже есть: длина \(4\).
• Любой другой путь начинается с ВД и уже на первом шаге длиннее \(5 > 4\). Так как все длины положительны, дальше путь может только удлиняться — обогнать 4 он не сможет.

Для полноты перечислим альтернативы: \[ \text{В–Д–Г}=5+5=10,\quad \text{В–Д–Б–Г}=5+5+1=11,\quad \text{В–Д–Е–Г}=5+6+3=14 . \]

Минимум — 4 км, путь ВГ.

3. Проверка

Иду по найденному пути по таблице: В–Г — в строке «В» в столбце «Г» стоит 4, в строке «Г» в столбце «В» тоже 4. Дорога существует, длина 4. Короче быть не может: единственный другой первый шаг из В стоит 5, а длины дорог не бывают отрицательными.

4. Принцип для похожих задач

1. Перепиши таблицу в список рёбер (не забудь, что она симметрична).
2. Смотри, какие дороги выходят из начального пункта: часто их всего 1–2, и перебор резко сокращается.
3. Сравнивай суммы длин: как только частичный путь стал длиннее уже найденного целого, его можно отбросить (это и есть идея алгоритма Дейкстры).
4. Ответ записывай цепочкой букв без пробелов: ВГ. Если дорог между пунктами нет совсем, ответ −1.