##master-page:VMSHClassTemplate
##master-date:Unknown-Date
#format wiki
#language ru
= Графы: разбор задач и продолжение =

  * Генерация графов различного типа на примере [[../2013-02-08|задачи генератора с прошлого раза]]
  * Обход графа вширь: решение задачи достижимости и кратчайшего пути
  * Обход графа вглубь: +решение задачи проверки цикличности орграфа
  * Графы с весами. Задача построения кратчайшего пути. Алгоритм Дейкстры и алгоритм Флойда.

=== Домашнее задание ===

  1. {i} Прочитать про алгоритмы Флойда и Дейкстры [[http://informatics.mccme.ru/moodle/course/view.php?id=6|на сайте MCCME]]
  1. Решить [[../2013-02-08|задачи проверки свойств графа (4 и 5) с прошлого раза]]
  1. Таблица N×N содержит стоимости прямого проезда из города '''i''' в город '''j''' (i<N, j<N, i≠j). Стоимость проезда не превышает S, если из города i в город j проезда нет, в таблице стоит S*N.
   1. Определить минимальную стоимость проезда из города A в город B с учётом возможных пересадок
   1. составить таблицу минимальной стоимости проезда из любого города в любой
    * Решение двух предыдущих задач: [[attachment:2013-02-15.trip.py]]
   1. …вывести также любой маршрут из A в B с минимальной стоимостью проезда

==== Условные обозначения ====
 . {o} — тема по Linux
 . <!> ­— тема повышенной сложности
 . {i} — теоретическое задание
 . {*} — тема для самостоятельного изучения

----
CategoryClass CategoryVmsh