Метод Дейкстры

Введение

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

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

В графе не существует пары рёбер, которые соединяют одинаковую пару вершин. Одной из актуальных задач в теории графов является задача об определении минимальных путей во взвешенном связном графе. Кратчайшим (минимальным) путём между выбранными вершинами графа называется маршрут, проходящий по его рёбрам, у которого суммарный вес рёбер будет самым маленьким. Примером может служить следующая реальная задача. Предположим в какой-то стране находятся какое-то количество городов с соединяющими их дорогами. Каждая дорога определяется расстоянием между городами, которые она соединяет, то есть своей длиной. Задача формулируется так. Необходимо добраться из одного города в другой по самому короткому маршруту.

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

Алгоритм учёного из Нидерландов Эдсгера Дейкстры позволяет определить все самые короткие маршруты из заданной начальной вершины графа ко всем другим вершинам. Именно при его использовании и наличии всех требуемых данных можно определить в какой последовательности нужно проезжать по дорогам, чтобы попасть из заданного исходного города (точки) до всех других городов с минимальными затратами. Или, например, куда наиболее выгодно осуществлять экспорт нефти и так далее. К недостаткам этого алгоритма можно отнести тот факт, что он не может быть применён е графам, имеющим рёбра отрицательного веса. То есть нельзя, к примеру, анализировать какие-либо убыточные маршруты методом Дейкстры.

Чтобы реализовать данный алгоритм в виде программы, необходимо сформировать два массива. Первый массив логики visited, предназначается для сохранения информационных данных об уже пройденных вершинах, а второй массив числовой distance, в котором будет храниться вычисленные самые короткие маршруты. Предполагаем, что есть граф G = (V, E). В начале все вершины графа, которые входят во множество V, помечаются как «ещё не посещались». Это означает, что все компоненты массива visited получают метку false. Так как наиболее оптимальные (по выгоде) маршруты ещё нужно будет определить, то во все компоненты массива distance заносится численная величина, которая гарантировано превышает любой потенциальный маршрут (как правило, это должна быть бесконечность, но при программной реализации применяют наибольшую величину фактического вида данных). Исходной точкой пути назначается вершина s, и она получает путь равный нулю: distance[s]=0, поскольку не существует ребра, соединяющего s и s (петли в алгоритме не предусмотрены). Затем определяются все вершины по соседству с s (то есть соединённые рёбрами из s) и последовательно анализируется, а вернее вычисляется цена пути из s в эти вершины (обозначим их t и u):

1. distance[t]=distance[s]+вес инцидентного s и t ребра.
2. distance[u]=distance[s]+вес инцидентного s и u ребра.

Однако существует вероятность того, что к другим вершинам из s может быть более одного пути. Поэтому стоимость маршрута к этой вершине в массиве distance нужно будет проверять повторно, и тогда большая величина отбрасывается, а самая маленькая записывается в параметры этой вершины. Когда заканчивается анализ соседних с s вершин, то она получает пометку о посещении: visited[s]=true, и активируется вершина с самым маленьким путём до s. Предположим, что путь из s в u более короткий, чем расстояние между s и t, то есть, вершина u активируется и начинается анализ путей уже к её соседям, исключая уже обработанную вершину s. Затем, пометку пройденной вершины получает u: visited[u]=true, активируется следующая вершина t, и описанная выше операция выполняется уже с ней. Выполнение алгоритма Дейкстры будет продолжаться до момента, пока не будут проанализированы все достижимые из s вершины.

Рассмотрим действие этого алгоритма на конкретном примере и определим все минимальные маршруты между начальной и всеми другими вершинами. Число рёбер приведённого ниже графа равняется семи (|E|=7), а число его вершин равно шести (|V|=6). Данный граф является взвешенным, то есть каждому его ребру соответствует числовое значение (вес). Это означает, что стоимость маршрута не определяется только числом рёбер между двумя заданными вершинами.

Рисунок 1. Граф. Автор24 — интернет-биржа студенческих работ

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

2←1+0

3←4+0

5←2+0

Как выше указывалось, полученные величины придаются вершинам только тогда, когда они имеют меньший вес, чем тот, который обозначен на текущий момент. И поскольку все три числа меньше, чем бесконечность, то они будут новыми значениями, которые определяют путь из первой вершины до второй, третьей и пятой вершин. Затем текущая активная вершина получает метку посещённой и активируется соседняя вершина с номером два, так как она самая ближняя по весу к предыдущей активной. В свою очередь вершина номер два имеет только одного не проанализированного соседа с номером четыре (первая вершина имеет пометку посещённой), дистанция до которого равняется девяти. Но по условиям задачи нужно определить длину маршрута из исходной вершины. Для этого необходимо прибавить значение присвоенное второй вершине к весу дуги, соединяющей её с вершиной четыре.

4←1+9

И так далее. Выполнение алгоритма завершится, когда все вершины получат метку посещённых.