Содержание материала
Интуитивное понимание алгоритма
Можно представить, что мы поджигаем вершину \(s\). Каждый шаг алгоритма — это распространение огня на соседние вершины. Понятно, что огонь доберётся до вершины по кратчайшему пути.
Заметьте, что этот алгоритм очень похож на DFS — достаточно заменить очередь на стек и поиск в ширину станет поиском в глубину. Действительно, оба алгоритма при обработке вершины просто записывают всех непосещенных соседей, в которые из неё есть ребро, в структуру данных, и после этого выбирает следующую вершину для обработки в структуре данных. В DFS это стек (благодаря рекурсии), поэтому мы сначала записываем соседа, идем в обрабатываем его полностью, а потом начинаем обрабатывать следующего соседа. В BFS это очередь, поэтому мы кидаем сразу всех соседей, а потом начинаем обрабатывать вообще другую вершину — ту непосещенную, которую мы положили в очередь раньше всего.
Оба алгоритма позволяют обойти граф целиком — посетить каждую вершину ровно один раз. Поэтому они оба подходят для таких задач как: * поиск компонент связности * проверка графа на двудольность * построение остова
Первый шаг
Минимальную метку имеет вершина 1. Её соседями являются вершины 2, 3 и 6. Обходим соседей вершины по очереди. Первый сосед вершины 1 – вершина 2, потому что длина пути до неё минимальна. Длина пути в неё через вершину 1 равна сумме кратчайшего расстояния до вершины 1 (значению её метки) и длины ребра, идущего из 1-й во 2-ю, то есть 0 + 7 = 7. Это меньше текущей метки вершины 2 (10000), поэтому новая метка 2-й вершины равна 7. 
Аналогично находим длины пути для всех других соседей (вершины 3 и 6). Все соседи вершины 1 проверены. Текущее минимальное расстояние до вершины 1 считается окончательным и пересмотру не подлежит. Вершина 1 отмечается как посещенная.
Видео
Корректность
Утверждение. > 1. Расстояния до тех вершин, которые были добавлены в очередь, посчитаны корректно. > 2. Вершины лежат в очереди в порядке неубывания расстояния, притом разность между кратчайшими расстояними до вершин в очереди не превосходит \(1\).
Докажем это по индукции по количеству итераций алгоритма (итерация — извлечение вершины из очереди и дальнейшая релаксация).
База очевидна. Переход. Сначала докажем первую часть. Предположим, что \(dist[v] + 1 < dist[u]\), но \(dist[v] + 1\) — некорректное расстояние до вершины \(u\), то есть \(dist[v] + 1 \neq d(u)\). Тогда по лемме 1: \(d(u) < dist[v] + 1\). Рассмотрим предпоследнюю вершину \(w\) на кратчайшем пути от \(s\) до \(u\). Тогда по лемме 2: \(d(w) + 1 = d(u)\). Следовательно, \(d(w) + 1 < dist[v] + 1\) и \(d(w) < dist[v]\). Но тогда по предположению индукции \(w\) была извлечена раньше \(v\), следовательно, при релаксации из неё в очередь должна была быть добавлена вершина \(u\) с уже корректным расстоянием. Противоречие. Теперь докажем вторую часть. По предположению индукции в очереди лежали некоторые вершины \(u_1, u_2, \dots u_k\), для которых выполнялось следующее: \(dist[u_1] \leq dist[u_2] \leq \dots \leq dist[u_k]\) и \(dist[u_k] — dist[u_1] \leq 1\). Мы извлекли вершину \(v = u_1\) и могли добавить в конец очереди какие-то вершины с расстоянием \(dist[v] + 1\). Если \(k = 1\), то утверждение очевидно. В противном случае имеем \(dist[u_k] — dist[u_1] \leq 1 \leftrightarrow dist[u_k] — dist[v] \leq 1 \leftrightarrow dist[u_k] \leq dist[v] + 1\), то есть упорядоченность сохранилась. Осталось показать, что \((dist[v] + 1) — dist[u_2] \leq 1\), но это равносильно \(dist[v] \leq dist[u_2]\), что, как мы знаем, верно.
А* (А со звездочкой)
Впервые описан в 1968 году Питером Хартом, Нильсом Нильсоном и Бертрамом Рафаэлем. Данный является расширением алгоритма Дейкстры, ускорение работы достигается за счет эвристики — при рассмотрении каждой отдельной вершины переход делается в ту соседнюю вершину, предположительный путь из которой до искомой вершины самый короткий. При этом существует множество различных методов подсчета длины предполагаемого пути из вершины. Результатом работы также будет кратчайший путь. О реализации алгоритма читайте в .
Алгоритм Форда-Беллмана
n * mПсевдокод [ править]
Реализация с восстановлением пути
Восстановление пути для алгоритма Дейкстры реализуется точно так же, как и для BFS: при успешном улучшении пути в вершину \(u\) через вершину \(v\), мы запоминаем, что \(prev[v] = u\). После окончания работы алгоритма используем массив \(prev\) для восстановления пути в обратном направлении.
Реализация на C++:
Шестой шаг
Таким образом, кратчайшим путем из вершины 1 в вершину 5 будет путь через вершины 1 — 3 — 6 — 5, поскольку таким путем мы набираем минимальный вес, равный 20. Займемся выводом кратчайшего пути. Мы знаем длину пути для каждой вершины, и теперь будем рассматривать вершины с конца. Рассматриваем конечную вершину (в данном случае — вершина 5), и для всех вершин, с которой она связана, находим длину пути, вычитая вес соответствующего ребра из длины пути конечной вершины. Так, вершина 5 имеет длину пути 20. Она связана с вершинами 6 и 4. Для вершины 6 получим вес 20 — 9 = 11 (совпал). Для вершины 4 получим вес 20 — 6 = 14 (не совпал). Если в результате мы получим значение, которое совпадает с длиной пути рассматриваемой вершины (в данном случае — вершина 6), то именно из нее был осуществлен переход в конечную вершину. Отмечаем эту вершину на искомом пути. Далее определяем ребро, через которое мы попали в вершину 6. И так пока не дойдем до начала. Если в результате такого обхода у нас на каком-то шаге совпадут значения для нескольких вершин, то можно взять любую из них — несколько путей будут иметь одинаковую длину.