Замыкание транзитивного бинарного отношения
Какое-нибудь описание.
- Подтема 1
Подтема 2
Домашнее задание
Почитать про Алгоритм Флойда–Уоршелла и Алгоритм Дейкстры в Википедии - Дана таблица, содержащая стоимость проезда из города i в город k по N городам (необязательно симметричная). Проезд стоит от 1 до 1000р, если проезда нет, в таблице записано N**2*1000. Вводятся два номера городов -- A и B. Вычислить минимальную стоимость проезда из A в B с учётом пересадок.
Решение фактически совпадает с описанием алгоритма floyd-warshell.py
- Решить данным алгоритмом задачу о длине минимального пути в лабиринте
Алгоритм придётся модифицировать с учётом доступности клеток лабиринта. Получится алгоритм Дейкстры (см. выше) labdijkstra.py
Новая версия генератора лабиринтов (третий параметр включает непроходимость): labpur.py
Условные обозначения
- — тема по Linux
— необязательная тема - — теоретическое задание
— тема для самостоятельного изучения