Лекция 14. Поиск оптимального пути в графе. Часть 2

  1. 00:10Задача. Поиск кратчайшего пути во взвешенном графе
  2. 01:06Определение. Релакс (расслабление вершины относительно другой вершины)
  3. 04:42Определение. Очередь с приоритетами
  4. 09:422 случай. Любой граф с положительными весами. Алгоритм Дейкстры
  5. 35:063 случай. Любой граф без отрицательных циклов. Алгоритм Беллмана-Форда
  6. 47:47Определения. Сеть. Поток сети. Величина потока
  7. 52:38Задача. Найти такой поток в сети, который максимизирует величину потока
  8. 01:10:18Определения. Разрез сети. Пропускная способность разреза. Поток через разрез