Задание для групп БЛК-151/152 бакалавриата ВШЭ по курсу теории алгоритмов
Пакет предоставляет класс Router, вычисляющий кратчайший по времени путь между двумя станциями Московского метро.
Рекомендуется установка в виртуальное окружение. Режим editable (флаг -e) позволяет тестировать код сразу после внесения изменений, без дополнительной переустановки:
$ git clone git@github.com:<username>/pymetro.git
$ cd pymetro
$ python3 -m venv .env
$ . .env/bin/activate
$ pip install -e .
In [1]: from pymetro import *
In [2]: source, target = Station(7), Station(46)
In [3]: source, target
Out[3]: (<Station: Красные Ворота (line 1)>, <Station: Бауманская (line 3)>)
In [4]: r = Router().make_route(source, target)
In [5]: r.path
Out[5]:
[<Station: Красные Ворота (line 1)>,
<Station: Чистые пруды (line 1)>,
<Station: Сретенский бульвар (line 10)>,
<Station: Чкаловская (line 10)>,
<Station: Курская (line 3)>,
<Station: Бауманская (line 3)>]
In [6]: r.time
Out[6]: 795
Данные для построение графа метро находятся в файле data.py.
Вам необходимо реализовать класс Router из файла router.py. Остальной код следует оставить без изменений.
Соблюдайте типы, указанные в аннотациях к функциям: make_route принимает объекты класса Station, а возвращает объект класса Route.
Кратчайший путь следует находить алгоритмом Дейкстры. Для его реализации понадобится очередь с изменяемым приоритетом. Её можно взять из модуля heapdict (он уже прописан в зависимостях).
Для проверки задания необходимо прислать pull-request (PR) в этот репозиторий. При успешной сдаче PR закрывается без мёржа, оценка будет сообщаться в комментариях.