Задание 4: кратчайший путь в графе

1. 1. Из A выходят два ребра: в B (3) и в C (9). Значит маршрутов будет две группы.
2. 2. Группа «через B»: A–B–C–E = 3 + 2 + 6 = 11; A–B–C–D–E = 3 + 2 + 1 + 2 = 8; A–B–D–E = 3 + 6 + 2 = 11; A–B–D–C–E = 3 + 6 + 1 + 6 = 16.
3. 3. Группа «через C»: A–C–E = 9 + 6 = 15; A–C–D–E = 9 + 1 + 2 = 12; A–C–B–D–E = 9 + 2 + 6 + 2 = 19.
4. 4. Сравниваем все суммы: 8, 11, 11, 12, 15, 16, 19. Наименьшая — 8.
5. 5. Кратчайший путь оказался самым длинным по числу рёбер: A–B–C–D–E, целых четыре участка. Прямая дорога A–C длиной 9 в кратчайший путь вообще не вошла.
6. 6. В ответ записываем только число: 8.

Ответ: Ответ: 8

1. 1. Ставим пометки: A = 0, остальные пока не определены.
2. 2. Обрабатываем A. Соседи: B получает 0 + 3 = 3, C получает 0 + 9 = 9.
3. 3. Наименьшая непомеченная — B (3). Обрабатываем её: C можно улучшить до 3 + 2 = 5 (это меньше 9), D получает 3 + 6 = 9.
4. 4. Наименьшая непомеченная — C (5). Обрабатываем: D улучшаем до 5 + 1 = 6 (меньше 9), E получает 5 + 6 = 11.
5. 5. Наименьшая непомеченная — D (6). Обрабатываем: E улучшаем до 6 + 2 = 8 (меньше 11).
6. 6. Осталась одна вершина E с пометкой 8 — она и становится окончательной. Ответ совпал с перебором: 8.
7. 7. Обрати внимание, как пометка C менялась: сначала 9, потом 5. Именно это уточнение и даёт правильный ответ; тот, кто зафиксировал 9 сразу, получит 12 вместо 8.

Ответ: Ответ: 8

1. 1. Сначала выписываем все дороги, ведущие в F: A—F (9), B—F (6), E—F (7). Значит, попасть в F можно только через A напрямую, через B или через E.
2. 2. Считаем лучшие расстояния до этих пунктов от A: до B — 1 (напрямую), до E — через C: A—C (1) + C—E (1) = 2 (напрямую из A дороги в E нет, через D вышло бы 2 + 5 = 7).
3. 3. Складываем три варианта: напрямую A—F = 9; через B: 1 + 6 = 7; через E: 2 + 7 = 9.
4. 4. Наименьшее: 7, путь A—B—F.
5. 5. Почему это надёжнее полного перебора: маршрутов в такой таблице десятки, а дорог в конечный пункт всего три. Считать надо только лучшие пути до этих трёх пунктов — работа сокращается в разы.

Ответ: 7

1. 1. Дороги в F: D—F (6) и E—F (1). Значит, нужны лучшие расстояния от A до D и до E.
2. 2. До B: 2. До C: напрямую 4 или через B 2 + 1 = 3 — берём 3.
3. 3. До D: через B 2 + 7 = 9 или через C 3 + 3 = 6 — берём 6.
4. 4. До E: через C 3 + 8 = 11 или через D 6 + 2 = 8 — берём 8.
5. 5. Варианты финиша: через D 6 + 6 = 12; через E 8 + 1 = 9. Кратчайший путь 9: A—B—C—D—E—F.
6. 6. Важная деталь: путь из пяти дорог оказался короче пути из двух. Число участков ничего не говорит о длине — сравнивать надо только суммы.

Ответ: 9

1. 1. Вариант первый — прямая дорога A—C: 5 км.
2. 2. Вариант второй — через B: A—B (1) + B—C (1) = 2 км.
3. 3. Кратчайший путь — 2, и он идёт в обход, хотя прямая дорога существует.
4. 4. Вывод, который спасает на экзамене: наличие прямой дороги не значит, что она кратчайшая. Проверять обходные пути обязательно — именно на этом построена половина заданий линии 4.
5. 5. Проверка на смысл: в таблице такие случаи видны сразу — в строке стоит одно большое число и несколько маленьких.

Ответ: 2

1. 1. Замысел: храним дороги словарём, идём по методу пометок — начинаем с пункта A с расстоянием 0 и каждый раз берём ближайший ещё не обработанный пункт, обновляя расстояния до его соседей. Это машинная запись того же приёма, которым решали задание вручную.
2. 2. Код целиком (Python): roads = {('A','B'):1, ('A','C'):1, ('A','D'):2, ('A','F'):9, ('B','C'):7, ('B','D'):3, ('B','F'):6, ('C','D'):3, ('C','E'):1, ('D','E'):5, ('E','F'):7} / INF = 10**9 / dist = {v: INF for v in 'ABCDEF'} / dist['A'] = 0 / done = set() / while len(done) < 6: / v = min((u for u in dist if u not in done), key=lambda u: dist[u]) / done.add(v) / for (a, b), w in roads.items(): / for x, y in ((a, b), (b, a)): / if x == v and dist[v] + w < dist[y]: / dist[y] = dist[v] + w / print(dist['F']).
3. 3. Трассировка: сначала обрабатывается A (dist: B = 1, C = 1, D = 2, F = 9), затем B (D остаётся 2, потому что 1 + 3 = 4 больше; F = 1 + 6 = 7), затем C (E = 1 + 1 = 2), затем D, затем E (F = 2 + 7 = 9 — больше семи, не обновляется). Печатается 7, что совпало с ручным ответом.
4. 4. Что проверить перед сдачей: каждая дорога должна работать в обе стороны (за это отвечает строка с ((a, b), (b, a))) и вывод должен быть один, после цикла. Обе вещи прямо названы в критериях задания 16.
5. 5. Как сохранять: текстовый файл с расширением .py.

Ответ: paths.py: метод пометок, печатает 7 для таблицы из первого разбора