Алгоритмы нахождения кратчайших путей между вершинами графа

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

Путь между вершинами А и В графа считается кратчайшим, если:

эти вершины соединены минимальным числом ребер (в случае, если граф не является взвешенным);
сумма весов рёбер, соединяющих эти вершины, минимальна (для взвешенного графа).

Есть множество алгоритмов определения кратчайшего пути между вершинами графа, в том числе:

1) алгоритм построения дерева решений;

2) алгоритм Дейкстры;

3) метод динамического программирования.

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

Алгоритм Дейкстры служит для нахождения кратчайшего пути между одной конкретной вершиной (источником) и всеми остальными вершинами графа.

Суть алгоритма состоит в следующем. Каждой вершине графа ставится в соответствие метка — минимальное известное расстояние от источника до этой вершины. Метка самого источника полагается равной 0. Алгоритм работает пошагово — на каждом шаге он «посещает» одну вершину и пытается уменьшать метки.

На первом шаге расстояние от источника до всех остальных вершин неизвестно. Метки вершин (кроме источника) считаются равными бесконечности, все вершины считаются непосещёнными.

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

Рассмотрим работу алгоритма на примере. На рисунке 3.12 кружками обозначены вершины графа, в кружки вписаны имена вершин. Вершины соединены линиями — рёбрами графа. Около каждого ребра обозначен его «вес» — длина пути. Рядом с каждой вершиной дана метка — длина кратчайшего пути в эту вершину из вершины А: для вершины А — это 0, для всех других вершин она неизвестна и обозначена знаком «бесконечность».

Алгоритм Дейкстры. Начальное состояние

Минимальную метку (0) имеет вершина А. Её соседи — вершины В, С, D. Очерёдность рассмотрения соседей: В, D, С. После изменения их меток получим результат, представленный на рисунке 3.13.

Алгоритм Дейкстры. Шаг 1

Окончание >>>