Семинар 8.

1.	Алгоритм Флойда-Уоршелла(-Роя) ищет длины кратчайших путей между всеми вершинами
	в графе. В нём применяется динамика по номеру максимально разрешённой в пути
	вершины. Подробнее: сначала нумеруются все вершины от 1 до n. Затем начинаем
	считать величины D(i,j,k) — длина кратчайшего пути из i в j, проходящая только
	через вершины с номером не более k. D(i,j,0) — это длина ребра (i,j), или
	бесконечность, если ребро отсутствует. Когда мы рассматриваем новую вершину k,
	у нас есть два варианта: либо через k-ю вершину нельзя провести путь короче,
	чем провели до этого, и тогда D(i,j,k) совпадает с D(i,j,k-1), либо провести
	более короткий путь можно, и тогда длина этого пути равна сумме длин кратчайших
	путей от i до k и от k до j. Таким образом, получаем рекуррентную формулу:
	D(i,j,k) = min(D(i,j,k-1), D(i,k,k-1) + D(k,j,k-1)). Алгоритм работает за время
	O(V^3) и использует O(V^2) памяти.

2.	Заметим, что величины D(i,i,k) — это длины кратчайших циклов, проходящих через
	вершину i. И если в какой-то момент D(i,i,k) становится отрицательной, тогда
	(и только тогда) в графе есть цикл отрицательной длины, проходящий через i, и
	значит расстояния до вершин, из которых этот цикл достижим, можно сделать сколь
	угодно малыми.

3.	Алгоритм Флойда также позволяет восстанавливать кратчайшие пути, а не только
	считать их длины. Для этого нужно поддерживать матрицу N, каждый элемент N(i,j)
	которой содержит наибольший номер вершины, через которую пройдёт кратчайший путь
	из i в j. Обновляется это значение каждый раз, когда в рекуррентном выражении,
	в минимуме мы вибираем второе число. А путь из i в j восстанавливается также
	рекуррентным образом: это конкатенация путей из i в N[i,j] и из N[i,j] в j.

4.	Алгоритм Джонсона решает ту же задачу, что и алгоритм Флойда, но пытается делать
	это быстрее. Для нахождения всех кратчайших путей, мы будем из каждой вершины
	запускать алгоритм Дейкстры. Но перед тем как это делать, нам нужно избавиться
	от рёбер отрицательной длины, так как алгоритмы Дейкстры с ними не работает.
	Итак, мы хотим переназначить веса рёбрам таким образом, чтобы соотношения длин
	путей не поменялось, а рёбер отрицательной длины не было. Для этого мы временно
	добавим к нашему графу вершину s, из которой пустим во все остальные вершины
	рёбра нулевой длины. Теперь запустим из s алгоритм Форда-Беллмана, он найдёт
	нам длины p(v) кратчайших путей от s до каждой вершины графа v. Теперь мы
	назначим всем рёбрам новые длины по формуле: l'(u,v) = l(u,v) + p(u) - p(v).
	После такого преобразования, соотношения длин путей не изменятся, так как
	изменение длины пути зависит только от начальной и конечно точек этого пути:
	L'(P) = l(u,w) + p(u) - p(w) + l(w,t) + p(w) - p(t) + ... = L(P) + p(u) - p(v).
	А отрицательных рёбер не останется потому что кратчайшее расстояние от вершины
	s до любой другой в новом графе равно L'(P) = L(P) + p(s) - p(v) = 0, а если
	есть отрицательное ребро (u,v), то можно найти путь до v длины меньше нуля.
	Время работы алгоритма зависит от того, как был реализован алгоритм Дейкстры,
	время работы алгоритма Форда-Беллмана по сравнению с ним будет мало. Итак,
	общее время работы алгоритма можно оценить как O(V(E+V)log(V)), или O(EVlog(V)).