Путь по таблице родителей

ЛёгкаяДописатьГлава 7

#алгоритм Дейкстры#восстановление путиid: ga-restore-path

После работы алгоритма Дейкстры остаётся таблица родителей: parents[x] — узел, из которого выгоднее всего прийти в x. Допишите restore_path(parents, start, goal): функция восстанавливает путь от start до goal в виде списка узлов. Если goal недостижим (его нет в таблице и он не совпадает со start), она возвращает []. Пропуски помечены # TODO.

Пример

parents = {"B": "start", "A": "B", "fin": "A"}
restore_path(parents, "start", "fin")    # ["start", "B", "A", "fin"]
restore_path(parents, "start", "start")  # ["start"]
restore_path(parents, "start", "X")      # []

Решение

def restore_path(parents: dict[str, str], start: str, goal: str) -> list[str]:
    """Путь от start до goal по таблице родителей или [] если goal недостижим."""
    if goal != start and goal not in parents:
        return []
    path = [goal]
    # TODO: пока не дошли до start, добавляйте в path родителя последнего узла
    # TODO: верните путь в порядке от start к goal
    return path

Вывод

tests.py — только для чтения
PARENTS = {"B": "start", "A": "B", "fin": "A", "C": "start"}


def test_example():
    """Пример: start → B → A → fin"""
    got = restore_path(PARENTS, "start", "fin")
    assert got == ["start", "B", "A", "fin"], f"получено {got!r}"


def test_one_edge():
    """Путь из одного ребра"""
    got = restore_path(PARENTS, "start", "C")
    assert got == ["start", "C"], f"получено {got!r}"


def test_same():
    """goal == start → [start]"""
    got = restore_path(PARENTS, "start", "start")
    assert got == ["start"], f"получено {got!r}"


def test_unreachable():
    """goal нет в таблице → []"""
    got = restore_path(PARENTS, "start", "X")
    assert got == [], f"получено {got!r}"


def test_empty_table():
    """Пустая таблица"""
    assert restore_path({}, "s", "s") == ["s"], "до себя путь из одного узла"
    assert restore_path({}, "s", "t") == [], "без таблицы до t не добраться"


def test_long_chain():
    """Цепочка из 1000 узлов"""
    parents = {f"n{i}": f"n{i - 1}" for i in range(1, 1000)}
    got = restore_path(parents, "n0", "n999")
    assert got == [f"n{i}" for i in range(1000)], f"начало: {got[:3]}, конец: {got[-3:]}"

Можно решать и в своём редакторе: «Скопировать с тестами» и запустите python3 restore_path.py — тесты те же, результат покажет ✓ / ✗ и итог.

Подсказка 1
Таблица родителей хранит путь задом наперёд: от goal по parents можно дойти до start.
Подсказка 2
Собирайте узлы в список, пока не дойдёте до start, затем разверните список: path[::-1].

solution.py

def restore_path(parents: dict[str, str], start: str, goal: str) -> list[str]:
    """Путь от start до goal по таблице родителей или [] если goal недостижим."""
    if goal != start and goal not in parents:
        return []
    path = [goal]
    while path[-1] != start:
        path.append(parents[path[-1]])
    return path[::-1]