Алгоритмы поиска кратчайших путей

Источник:
  Электронный учебник по информатике,
  школа №9 им. А.С.Пушкина, г.Пермь
  http://school9.perm.ru/Tutorial/Graph/chapter2/shortest_way.htm

Этот тип алгоритмов предназначен для поиска кратчайших путей между некоторыми вершинами графа. Это самые распространённые, известные и часто используемые алгоритмы на графах, можно сказать, фундаментальные алгоритмы. Рекомендуется изучить их все, кроме того, описание работы одного алгоритма часто ссылается на работу другого, описанного ранее. Стоит ещё заметить, что вы читаете учебник, а не справочник, поэтому в процесе объянения будут даваться практические советы.

Алгоритмы этой главы (не в пример остальным) нужно осознать глубинно, т.к. очень часто встречаются задачи на их модификации.

Теперь несколько определений.

Стоимостью или весом пути называется сумма весов всех его рёбер.

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

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

С поиском кратчайших путей связано такое понятие, как релаксация. Пусть у нас есть некоторый массив D и ребро из вершины U в вершину V весом в W. Релаксацией по ребру {U, V} называется следующее действие:

If D[V] > D[U] + W Then D[V] := D[U] + W;

Это понятие пригодится нам при изучении алгоритмов Дейкстры и Форда-Беллмана. В элементе D[I] при их реализации хранятся верхние оценки стоимостей кратчайших путей из некоторой стартовой вершины в I-ую. Вследствие релаксации эти оценки приближаются к действительным, а в конце концов достигают их. Посмотрите внимательно, что происходит при релаксации: нам известны стоимости некоторых путей до вершин U и V, а так же вес ребра {U, V}. Сходив из вершины U в вершину V по ребру {U,V}, мы получаем некоторый новый путь в вершину V, который является продолжением пути в вершину U. И если стоимость нового пути меньше уже имеющейся стоимости D[V], мы изменяем её на новую стоимость.

Если в графе между двумя вершинами нет ребра, мы полагаем его вес равным бесконечности. Это логично, поскольку в этом случае оно точно не будет входить ни в один кратчайший путь, т.к. любая конечная стоимость меньше бесконечной. Однако вопрос: как же хранить бсконечность в памяти компьютера? Вообще-то никак. Но это не страшно, не волнуйтесь! Всё уже придумано до нас. В качестве бесконечности мы будем использовать следующую константу:

Const Inf: Longint = MaxLongint div 2;

Почему MaxLongint - это понятно, нам нужно максимально возможное число для хранения, но вот почему div 2? Дело в том, что нам может понадобиться складывать два значения Inf, и в этом случае может возникнуть переполнение типа. Однако стоит помнить, что если Inf <= MaxW * (MaxN - 1), где MaxW - максимально возможный вес ребра, а MaxN - максимальное количество вершин (эти значения нужно брать из условий задачи), то у нас может ничего не получиться. Несложно заметить, что максимально возможная стоимость кратчайшего пути не может превышать MaxW * (MaxN - 1), а значение Inf должно превосходить все возможные стоимости, чтобы играть роль веса отсутствующего ребра (в случае с графом, в котором возможны веса отрицательного веса, минимальное значение Inf будет ещё больше, об этом будет рассказано при описании алгоритма Форда-Беллмана). Но чаще всего в жизни указанного значения для Inf бывает достаточно. Если это не так, то нужно работать со значением Inf отдельно, что делает реализацию алгоритмов более тормозной и громоздкой.

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

Снова напомним, что неориентированное ребро графа представляет собой два ориентированных ребра в списке рёбер, а матрица смежности неориентированного графа симметрична относительно своей главной диагонали, в ней A[I, J] = A[J, I] для любых I и J.

Ниже приведена сравнительная таблица работы алгоритмов данной главы. Она не предназначена для сиюминутного детального изучения. Рекомедуется сейчас просто взглянуть на неё, а когда Вы уже будете подробно знакомы с алгоритмами данного типа, рассмотреть её внимательней для систематизации усвоенного материала.

В этой таблице:

• Алгоритм - название алгоритма.
• Объект работы - описание графа, на котором работает данный алгоритм.
• Действие - что именно ищет алгоритм.
• Сложность - сложность работы алгоритма
  • Матрица - при представлении графа матрицей смежности.
  • Список - при представлении графа списком рёбер.
• Доп. память - количество дополнительной памяти, требуемой для работы алгоритма.
• Полезн. - рейтинг относительной полезности на практике по десятибальной шкале.