Лекция 9. Обход в глубину (продолжение). Кратчайшие пути

Обход в глубину в неориентированном графе. Ориентация рёбер (при первом просмотре). Деление рёбер на корневые и обратные. Дерево обхода. Отсутствие прямых и перекрёстных рёбер. Двусвязность, мосты и точки сочленения. Критерий точки сочленения: для корня дерева, в общем случае (на основе обратных рёбер из поддерева сына). Функция верхнего: самый верхний конец обратных рёбер из поддерева. Способы сравнения вершин: по высоте, по времени входа. Рекуррентное соотношение для функции верхнего.

Функция длины пути, аддитивная функция, веса рёбер. Цикл отрицательного веса: проблема и различные варианты постановки задачи. Кратчайший путь простой, все подпути кратчайшие. Классы алгоритмов: 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. Поведение с циклом отр. веса.