Графы: разбор задач и продолжение
Генерация графов различного типа на примере задачи генератора с прошлого раза
- Обход графа вширь: решение задачи достижимости и кратчайшего пути
- Обход графа вглубь: +решение задачи проверки цикличности орграфа
- Графы с весами. Задача построения кратчайшего пути. Алгоритм Дейкстры и алгоритм Флойда.
Домашнее задание
Прочитать про алгоритмы Флойда и Дейкстры на сайте MCCME Решить задачи проверки свойств графа (4 и 5) с прошлого раза
Таблица N×N содержит стоимости прямого проезда из города i в город j (i<N, j<N, i≠j). Стоимость проезда не превышает S, если из города i в город j проезда нет, в таблице стоит S*N.
- Определить минимальную стоимость проезда из города A в город B с учётом возможных пересадок
- составить таблицу минимальной стоимости проезда из любого города в любой
Решение двух предыдущих задач: 2013-02-15.trip.py
- …вывести также любой маршрут из A в B с минимальной стоимостью проезда
Условные обозначения
— тема по Linux 
— тема повышенной сложности - — теоретическое задание
— тема для самостоятельного изучения