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

Постановка задачи

Задача о кратчайшем пути - задача поиска кратчайшего пути от заданной вершины до заданной или до всех остальных.

Существует множество алгоритмов поиска кратчайшего пути:

Алгоритм Дейкстры находит кратчайший путь от одной из вершин графа до всех остальных. Алгоритм работает только для графов без рёбер отрицательного веса.
Алгоритм Форда-Беллмана - в отличие от алгоритма Дейкстры, способен корректно обработать отрицательный вес.
Алгоритм A* - эвристический алгоритм поиска.

Алгоритм Дейкстры (случай неотрицательных весов)

Идея алгоритма

Каждый раз, когда мы хотим посетить новый узел, мы выберем узел с наименьшим известным расстоянием.
Как только мы переместились в узел, мы проверяем каждый из соседних узлов. Мы вычисляем расстояние от соседних узлов до корневых узлов, суммируя стоимость ребер, которые ведут к этому новому узлу.
Если расстояние до узла меньше известного расстояния, мы обновим самое короткое расстояние.

На каждом шаге существует множество уже обработанных вершин и еще не обработанных.

Псевдокод

Инициализация:

for (v ∈ V)
	DIST[v] = ∞
	PREV[v] = ∅
DIST[v' ∈  V] = 0  // стартовая вершина
// Первый шаг:
H ← MakeQueue() // формирование очереди с приоритетами для вершины v'. Все инцидентные вершины попадают сюда
while (H ≠ ∅)
	v ← min(H) // из очереди с приоритетами выбирается минимальный DIST[v]
	for (vu ∈  E) //для каждого инцидентного ребра
		if (DIST[u] > DIST[v] + w(v,u) // если расстояние до вершины больше, чем то, по которому мы проходим - условие релаксации
			DIST[u] ← DIST[V] + w(v,u)
			PREV[u] ←
UpdatePriorities(H)

Сложность алгоритма

Худший случай - каждый путь содержит в себе все остальные ($v$ вершин). Если каждый такой путь будет хранится к каждой вершине, память будет $v^2$. Для оптимизации в каждой вершине хранится не весь путь, а только предыдущую вершину, из которой можно попасть в текущую.

Общая сложность алгоритма:

$O(v^2)$ при работе на массиве;
$O( ln⁡(v) )$ при работе на куче.

Если количество ребер небольшое, выгоднее использовать реализацию на куче, если же ребер намного больше, чем вершин, лучше использовать работу на массиве.

Применение алгоритма

Одно из применений алгоритма - маршрутизация. Например, алгоритм OSPF (Open Shortest Pass First). Каждый маршрутизатор строит некоторый граф и использует алгоритм Дейкстры в чистом виде.

Очередь приоритетов пуста. Работа алгоритма закончена.

Алгоритм Флойда-Уоршелла вычисления расстояний между всеми парами вершин

Алгоритм Флойда — Уоршелла — алгоритм для нахождения кратчайших расстояний между всеми вершинами взвешенного графа без циклов с отрицательными весами с использованием метода динамического программирования.

Идея алгоритма

Будем считать, что в графе $n$ вершин, пронумерованных числами от $0$ до $n - 1$. Граф задан матрицей смежности, вес ребра $i - j$ хранится в $w_{ij}$. При отсутствии ребра $i - j$ значение $w_{ij} = + \infty$, также будем считать, что $w%%_{%%ii} = 0$.

Пусть значение $a_{ij}^{k}$ равно длине кратчайшего пути из вершины $i$ в вершину $j$, при этом путь может заходить в промежуточные вершины только с номерами меньшими $k$ (не считая начала и конца пути). То есть $a_{ij}^{0}$ - это длина кратчайшего пути из $i$ в $j$, который вообще не содержит промежуточных вершин, то есть состоит только из одного ребра $i - j$, поэтому $a_{ij}^{0} = w{ij}$. Значение $a_{ij}^{1} = w{ij}$ равно длине кратчайшего пути, который может проходить через промежуточную вершину с номером 0, путь с весом $a_{ij}^{2}$ может проходить через промежуточные вершины с номерами 0 и 1 и т. д. Путь с весом $a{ij}^{n}$ может проходить через любые промежуточные вершины, поэтому значение $a_{ij}^{n}$ равно длине кратчайшего пути из $i$ в $j$.

Алгоритм Флойда последовательно вычисляет $a_{ij}^{0}, a_{ij}^{1}, a_{ij}^{2}, \dots, a_{ij}^{n}$, увеличивая значение параметра $k$. Начальное значение - $a_{ij}^{0} = w{ij}$.

Теперь предполагая, что известны значения $a_{ij}^{k - 1}$ вычислим $a_{ij}^{k}$. Кратчайший путь из вершины $i$ в вершину $j$, проходящий через вершины с номерами, меньшими, чем $k$ может либо содержать, либо не содержать вершину с номером $k - 1$. Если он не содержит вершину с номером $k - 1$, то вес этого пути совпадает с $a_{ij}^{k - 1}$. Если же он содержит вершину $k - 1$, то этот путь разбивается на две части: $i - (k - 1)$ и $(k - 1) - j$. Каждая из этих частей содержит промежуточные вершины только с номерами, меньшими $k - 1$, поэтому вес такого пути равен $a_{i, k - 1}^{k - 1} + a_{k - 1, j}^{k - 1}$. Из двух рассматриваемых вариантов необходимо выбрать вариант наименьшей стоимости, поэтому:

$$ a_{ij}^{k} = \min ( a_{ij}^{k - 1}, a_{i, k - 1}^{k - 1} + a_{k - 1, j}^{k - 1} ) $$

int A[n + 1][n][n];
for (int i = 0; i < n; ++i) { 
	for (int j = 0; j < n; ++j) 
		A[0][i][j] = W[i][j]; 
}
for (int k = 1; k <= n; ++k) { 
	for (int i = 0; i < n; ++i) 
		for (int j = 0; j < n; ++j) 
			A[k][i][j] = min(A[k-1][i][j], A[k-1][i][k-1] + A[k-1][k-1][j]); 
}

Внешний цикл в этом алгоритме последовательно перебирает все вершины, затем пытается улучшить пути из $i$ в $j$, разрешив им проходить через выбранную вершину. Упростим этот алгоритм, избавившись от «трехмерности» массива A: будем только хранить значение кратчайшего пути из $i$ в $j$ в $A[i][j]$, а при улучшении пути будем записать новую длину пути также в $A[i][j]$. Также изменим определение цикла по переменной $k$, заменив значение $k - 1$ на $k$.

int A[n][n];
for (int i = 0; i < n; ++i) { 
	for (int j = 0; j < n; ++j) 
		A[i][j] = W[i][j]; 
}
for (int k = 0; k < n; ++k) { 
	for (int i = 0; i < n; ++i) 
		for (int j = 0; j < n; ++j) 
			A[i][j] = min%%([%%i][j], A[i][k] + A[k][j]); 
}

Очевидно, что сложность такого алгоритма $O(n^3)$.

Обратите внимание, что при наличии ребер отрицательного веса значения $A[i][j]$ могут уменьшатся. Поэтому может оказаться, что значение $A[i][j]$ было равно $INF$, а затем оно уменьшилось благодаря наличию ребер отрицательного веса. В результате значение $A[i][j]$ оказалось меньше $INF$ (например, за счет объединения пути длиной $INF$ и пути отрицательного веса), но при этом все равно пути между вершинами $i$ и $j$ нет. Поэтому нужно либо ставить дополнительные проверки на то, что $A[i][k]$ и $A[k][j]$ не равны $INF$, либо значения, которые незначительно меньше $INF$, также считать отсутствием пути.

Алгоритм Флойда некорректно работает при наличии цикла отрицательного веса, но при этом если путь от $i$ до $j$ не содержит цикла отрицательного веса, то вес этого пути будет найден алгоритмом правильно. Также при помощи данного алгоритма можно определить наличие цикла отрицательного веса: если вершина $i$ лежит на цикле отрицательного веса, то значение $A[i][i]$ будет отрицательным после окончания алгоритма.

Для восстановления ответа необходим двумерный массив предшественников. Будем считать, что в $Prev[i][j]$ хранится номер вершины, являющейся предшественником вершины $j$ на кратчайшем пути из вершины $i$. Тогда при обновлении значения $A[i][j]$ нужно также обновить предшественника. А именно, если путь $i - j$ был обновлен на путь, проходящий через вершину $k$, то теперь предшественником вершины $j$ на пути из $i$ становится вершина, которая была ее предшественником на пути из $k$, то есть необходимо присвоить $Prev[i][j]=Prev[k][j]$.

Запишем алгоритм, который сохраняет предшественников, а также добавим проверки на существование пути:

vector < vector > A = W; 
vector < vector > Prev(n, vector(n, -1));
for (int k = 0; k < n; ++k) 
	for (int i = 0; i < n; ++i) 
		for (int j = 0; j < n; ++j) 
			if (A[i][k] < INF && A[k][j] < INF && A[i][k] + A[k][j] < A[i][j]) { 
				A[i][j] = A[i][k] + A[k][j]; Prev[i][j] = Prev[k][j]; 
			}

Восстановление пути из $i$ в $j$ аналогично ранее рассмотренным алгоритмам, только необходимо учесть двумерность массива Path:

vector Path;
while (j != -1) { 
	Path.push_back(j); j = Prev[i][j]; 
}
reverse(Path.begin(), Path.end());