Формальное описание

Для определенности положим, что вершины графа последовательно пронумерованы от . Алгоритм Флойда использует матрицу размера , в которой вычисляются длины кратчайших путей. Вначале для всех . Если дуга отсутствует, то . Каждый диагональный элемент матрицы равен .

Над матрицей выполняется итераций. После -й итерации содержит значение наименьшей длины путей из вершины в вершину , которые не проходят через вершины с номером, большим . Другими словами, между концевыми вершинами пути могут находиться только вершины, номера которых меньше или равны . На -й итерации для вычисления матрицы применяется следующая формула:

Н ижний индекс обозначает значение матрицы после -й итерации, но это не означает, что существует различных матриц, этот индекс используется для сокращения записи. Для вычисления ] проводится сравнение величины A_k-i[i, j] (т.е. стоимость пути от вершины к вершине без участия вершины или другой вершины с более высоким номером) с величиной A_k-1[i, k] + A_k-1[k, j] (стоимость пути от вершины до вершины плюс стоимость пути от вершины до вершины ). Если путь через вершину дешевле, чем , то величина изменяется.

Оценка сложности

Время выполнения этой программы, очевидно, имеет порядок поскольку в ней практически нет ничего, кроме вложенных друг в друга трех циклов. Доказательство "правильности" работы этого алгоритма также очевидно и выполняется с помощью математической индукции по , показывая, что на -й итерации вершина включается в путь только тогда, когда новый путь короче старого.

2. Алгоритм Данцига

При использовании алгоритма Данцига, вычисляются все кратчайшие пути в модели. Суть алгоритма состоит в выполнении исчерпывающего исследования, начиная с подсети из двух состояний и прибавляя по одному состоянию каждый раз для нахождения кратчайших путей в подсети. Когда число вершин в исследуемой подсети будет равным числу состояний модели, вычисления прекрааются. В алгоритме Данцига выполняется операций.

3. Алгоритм Розенхала

Алгоритм Розенхала является дальнейшим развитием алгоритма Данцига. Основная идея алгоритма состоит в том, что он позволяет провести класификацию вновь введенных дуг и избавится от лишних компонент. Алгоритм Розенхала позволяет существенно, по сравнению с алгоритмом Данцига, сократить время вычислений в сетях большой размерности. Вычислительная сложность алгоритма .

4. Алгоритм Дейкстры

Алгоритм Дейкстры — алгоритм на графах, изобретённый нидерландским ученым Э. Дейкстрой в 1959 году. Находит кратчайшее расстояние от одной из вершин графа до всех остальных. Алгоритм работает только для графов без рёбер отрицательного веса.

Формальное описание

В строке 1 производится обычная инициализация величин и , а в строке 2 инициализируется пустое множество вершин . В этом алгоритме поддерживается инвариант, согласно которому в начале каждой итерации цикла в строках 4-8 выполняется равенство . В строке 3 неубывающая очередь с приоритетами инициализируется таким образом, чтобы она содержала все вершины множества ; поскольку в этот момент , после выполнения строки 3 сформулированный выше инвариант выполняется. При каждой итерации цикла в строках 4-8 вершина и извлекается из множества и добавляется в множество 5, в результате чего инвариант продолжает соблюдаться. (Во время первой итерации этого цикла ) Таким образом, вершина и имеет минимальную оценку кратчайшего пути среди всех вершин множества — 5. Затем строках 7-8 ослабляются все ребра , исходящие из вершины . Если текущий кратчайший путь к вершине может быть улучшен в результате прохождения через вершину , выполняется ослабление и соответствующее обновление оценки величины и предшественника После выполнения строки 3 вершины никогда не добавляются в множество и что каждая вершина извлекается из этого множества и добавляется в множество 5 ровно по одному разу, поэтому количество итераций цикла while в строках 4-8 равно Поскольку в алгоритме Дейкстры из множества для помещения в множество 5 всегда выбирается самая "легкая" или "близкая" вершина, говорят, что этот алгоритм придерживается жадной стратегии.