Быстрый маршрут курьера

ЛёгкаяНайти ошибку2 ошибкиГлава 7

#алгоритм Дейкстры#взвешенный графid: ga-fastest-route

Курьер ищет самый быстрый маршрут: graph[a][b] — минуты на дорогу из a в b. Функция fastest_route(graph, start, goal) реализует алгоритм Дейкстры в стиле книги: таблицы стоимостей и родителей, на каждом шаге обрабатывается самый дешёвый узел. Она возвращает (время, путь) или (math.inf, []). В функции две ошибки — найдите и исправьте их.

Пример

graph = {"склад": {"A": 5, "B": 2}, "B": {"A": 1, "клиент": 9}, "A": {"клиент": 3}}
fastest_route(graph, "склад", "клиент")   # (6, ["склад", "B", "A", "клиент"])

Решение

import math


def fastest_route(graph: dict[str, dict[str, int]], start: str, goal: str) -> tuple[float, list[str]]:
    """(минимальное время, путь) от start до goal или (math.inf, [])."""
    nodes = set(graph) | {n for edges in graph.values() for n in edges} | {start, goal}
    costs = {n: math.inf for n in nodes}
    parents: dict[str, str] = {}
    processed: set[str] = set()
    while True:
        node = min((n for n in nodes if n not in processed), key=lambda n: costs[n], default=None)
        if node is None or costs[node] == math.inf:
            break
        processed.add(node)
        for neighbor, minutes in graph.get(node, {}).items():
            new_cost = minutes
            if new_cost < costs[neighbor]:
                costs[neighbor] = new_cost
                parents[neighbor] = node
    if costs[goal] == math.inf:
        return math.inf, []
    path = [goal]
    while path[-1] != start:
        path.append(parents[path[-1]])
    return costs[goal], path[::-1]

Вывод

tests.py — только для чтения
import math

GRAPH = {"склад": {"A": 5, "B": 2}, "B": {"A": 1, "клиент": 9}, "A": {"клиент": 3}}


def test_example():
    """Пример: 6 минут через B и A"""
    got = fastest_route(GRAPH, "склад", "клиент")
    assert got == (6, ["склад", "B", "A", "клиент"]), f"получено {got!r}"


def test_intermediate():
    """До A быстрее через B: 3 минуты"""
    got = fastest_route(GRAPH, "склад", "A")
    assert got == (3, ["склад", "B", "A"]), f"получено {got!r}"


def test_unreachable():
    """Недостижимый узел → (inf, [])"""
    got = fastest_route(GRAPH, "клиент", "склад")
    assert got == (math.inf, []), f"получено {got!r}"


def test_same_node():
    """start == goal → (0, [start])"""
    got = fastest_route(GRAPH, "склад", "склад")
    assert got == (0, ["склад"]), f"получено {got!r}"


def test_long_cheap_path():
    """Длинный путь из дешёвых рёбер лучше одного дорогого"""
    graph = {"s": {"t": 10, "a": 3}, "a": {"b": 3}, "b": {"t": 3}}
    got = fastest_route(graph, "s", "t")
    assert got == (9, ["s", "a", "b", "t"]), f"получено {got!r}"


def test_path_matches_cost():
    """Сумма весов по возвращённому пути равна времени"""
    graph = {"a": {"b": 4, "c": 1}, "c": {"b": 2, "d": 8}, "b": {"d": 1}, "d": {}}
    cost, path = fastest_route(graph, "a", "d")
    assert cost == 4, f"ожидалось 4, получено {cost!r}"
    total = sum(graph[x][y] for x, y in zip(path, path[1:]))
    assert total == cost and path[0] == "a" and path[-1] == "d", f"путь {path} стоит {total}, а время {cost}"

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

Подсказка 1
Все ответы получаются бесконечностью или неверными. Проверьте, как заполняется таблица стоимостей до цикла и как считается стоимость пути до соседа.
Подсказка 2
С какой стоимости начинается узел start? Посмотрите, что выберет min на первом шаге.
Подсказка 3
Стоимость пути до соседа — это стоимость пути до текущего узла плюс вес ребра, а не вес одного ребра.

solution.py

import math


def fastest_route(graph: dict[str, dict[str, int]], start: str, goal: str) -> tuple[float, list[str]]:
    """(минимальное время, путь) от start до goal или (math.inf, [])."""
    nodes = set(graph) | {n for edges in graph.values() for n in edges} | {start, goal}
    costs = {n: math.inf for n in nodes}
    costs[start] = 0
    parents: dict[str, str] = {}
    processed: set[str] = set()
    while True:
        node = min((n for n in nodes if n not in processed), key=lambda n: costs[n], default=None)
        if node is None or costs[node] == math.inf:
            break
        processed.add(node)
        for neighbor, minutes in graph.get(node, {}).items():
            new_cost = costs[node] + minutes
            if new_cost < costs[neighbor]:
                costs[neighbor] = new_cost
                parents[neighbor] = node
    if costs[goal] == math.inf:
        return math.inf, []
    path = [goal]
    while path[-1] != start:
        path.append(parents[path[-1]])
    return costs[goal], path[::-1]