6.9. Кратчайшие пути на графе

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

Пусть простой орграф, для каждого ребра и определен вес Найдем кратчайший путь между выделенными вершинами х и z (рис. 6.21). Несуществующие ребра будем считать ребрами с бесконечными весами. Сумму весов ребер в пути будем называть весом или длиной пути. Обозначим вес ребра Алгоритм поиска кратчайшего пути, начиная из вершины х, просматривает граф в ширину, помечая вершины значениями—метками их расстояний от Метки могут быть временные и окончательные. Временная метка вершины это минимальное расстояние от до когда в определении пути на графе учитываются не все маршруты из в Окончательная метка это минимальное расстояние на графе от до Таким образом, в каждый момент времени работы алгоритма некоторые вершины будут иметь окончательные метки, а остальная их часть — временные. Алгоритм заканчивается, когда вершина z получает окончательную метку, т.е. расстояние от до z.

Вначале вершине присваивается окончательная метка (нулевое расстояние до самой себя), а каждой из остальных — 1 вершин присваивается временная метка (бесконечность). На каждом шаге одной вершине с временной меткой присваивается окончательная и поиск продолжается дальше. На каждом шаге метки меняются следующим образом.

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

2. Определяется наименьшая из всех временных меток, которая и становится окончательной меткой своей вершины. В случае равенства меток выбирается любая из них.

Циклический процесс продолжается до тех пор, пока вершина z не получит окончательной метки. Легко видеть, что окончательная метка каждой вершины — это кратчайшее расстояние от этой вершины до начала

Рассмотрим пример поиска кратчайшего пути на графе, представленном на рис. 6.21.

Рис. 6.21. Простой взвешенный орграф

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

(см. скан)

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

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

Алгоритм 6.11. Алгоритм кратчайшего пути на орграфе

(см. скан)

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

а значение составит длину пути из Очередная новая вершина, претендующая на постоянную метку, обозначается через у.

• Сложность алгоритма. Алгоритм обращается к телу цикла не более раз, и число операций, требующихся при каждом таком обращении, равно Тогда сложность алгоритма составит

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

Программная реализация алгоритма поиска кратчайшего пути представлена в алгоритме 6.12 на Pascal'e, который близко соответствует множественному описанию алгоритма 6.11.

Алгоритм 6.12. Программа кратчайшего пути на орграфе

(см. скан)

(см. скан)

Рассмотрим пример расчета по программе алгоритма 6.12 поиска кратчайшего пути на графе, показанном на рис. 6.21. Исходные данные графа представляются матрицей весов его ребер в текстовом файле со следующей структурой:

• в первой строке определяется номер начальной вершины пути

• во второй строке определяется номер конечной вершины пути

• в третьей строке указывается количество Х вершин в графе;

• в следующих строках определяются строки матрицы весов графа.

Результаты расчетов сохраняются в выходном файле со следующей структурой: