Кратчайшие пути

Функция длины пути, аддитивная функция, веса рёбер. Цикл отрицательного веса: проблема и различные варианты постановки задачи. Кратчайший путь простой, все подпути кратчайшие. Классы алгоритмов: point-to-point, SSSP, APSP. Общая идея: поддерживаем (реализуемые) оценки сверху на длины, операция релаксации. Алгоритм Форда-Беллмана. Псевдокод. Доказательство, поведение с циклом отр. веса. Время работы O(V E). Альтернативный вывод алгоритма: динам. прогр. вперёд, R[k, v] - кратч. путь от s до v из <=k рёбер, переходы. Слияние ответов для разных k воедино. Алгоритм Флойда. Оценки d[i,j], (i,k,j)-релаксация, псевдокод. Время работы O(V^3). Доказательство: динам. прогр. назад, R[k, i, j] - кратч. путь из i в j с промеж. вершинами <=k. Рекуррентное соотношение. Слияние ответов для разных k. Поведение с циклом отр. веса. Алгоритм Дейкстры. Аксиоматика длины путей, примеры: аддитивная (неотр. веса), максимум. Пометки (W/G/B) вершин, их смысл. Инициализация. Идея: перекрашиваем серую вершину с мин. оценкой в чёрный. Просмотр вершины (функция Scan). Псевдокод алгоритма. Доказательство: обоснование перекрашивания G->B от противного. Время работы (аддитивная функция длины): O(V^2). Хранение серых вершин в куче. Бинарная куча O(E log V), k-ичная куча O(E log V / log(E/V)), фиббоначиева куча O(E + V log V). Восстановление пути, сохранение предка, дерево кратчайших путей.