Нахождение кратчайших путей с помощью алгоритма Дейкстры

3. Краткие теоретические сведения

4. Тестовый пример (вручную)

5. Содержательный (словесный) алгоритм

7. Реализация программы

9. Список литературы

Благодаря своему широкому применению, теория о нахождении кратчайших путей в последнее время интенсивно развивается.

Нахождение кратчайшего пути - жизненно необходимо и используется практически везде, начиная от нахождения оптимального маршрута между двумя объектами на местности (например, кратчайший путь от дома до университета), в системах автопилота, для нахождения оптимального маршрута при перевозках, коммутации информационного пакета в Internet и т.п.

Кратчайший путь рассматривается при помощи некоторого математического объекта, называемого графом.

Существуют три наиболее эффективных алгоритма нахождения кратчайшего пути:

· алгоритм Дейкстры (используется для нахождения оптимального маршрута между двумя вершинами);

· алгоритм Флойда (для нахождения оптимального маршрута между всеми парами вершин);

· алгоритм Йена (для нахождения k-оптимальных маршрутов между двумя вершинами).

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

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

алгоритм граф дейкстр

3. Краткие теоретические сведения

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

На первый взгляд кажется, что мы можем воспользоваться алгоритмом построения МОД, чтобы отбросить лишние ребра, а затем взять путь, соединяющий заданные вершины в построенном остовном дереве.

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

Напомним, что алгоритм построения МОД нацелен на поиск дерева с минимальным суммарным весом ребер. Рассмотрим, например, «циклический» граф, т.е. такой граф, в котором первая вершина соединена со второй, вторая с третьей, и так далее, а последняя вершина свою очередь соединена с первой. Такой граф представляет собой просто кольцо, каждая вершина в котором соединена с двумя другими. Пример такого графа с шестью вершинами приведен на рис. 6.7 (а).

Обратите внимание на то, что вес каждого ребра равен 1 за исключением ребра, соединяющего вершины А и В, вес которого равен 2. Алгоритм построения минимального остовного дерева выберет все ребра веса 1, отбросив единственное ребро веса 2. Это означает, однако, что путь от А к В в минимальном остовном дереве должен проходить через все остальные вершины, а его длина равна 5 (рис. 6.7 (6)). Ясно, что он не является кратчайшим, поскольку в исходном графе вершины А и В соединены ребром длины 2

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

В начале пути из вершины А у нас есть четыре возможных ребра. Из этих четырех ребер ребро АВ является кратчайшим. Поэтому мы добавляем к дереву вершину В (рис. 6.8 (в)) и смотрим, как следует обновить набор путей. С уже построенным деревом соединены теперь вершины Е и О, поэтому их следует добавить к кайме. Кроме того, мы должны посмотреть на вершину IЭ и сравнить прямой путь из нее в А, длина которого равна 7, с окольным путем через вершину В, длина которого равна 8. Прямой путь короче, поэтому приписанное к IЭ ребро менять не следует. Изучив теперь имеющиеся возможности, мы видим, что кратчайшим является путь из А в С длины 4. Ребро ВЕ короче, однако мы рассматриваем полную длину пути из А, а такой путь, ведущий в Е, имеет длину 5. Теперь к дереву кратчайших путей добавим вершину С (рис. 6.8 (г)). Посмотрев на граф, мы обнаруживаем, что можем пройти в вершину Г через вершину С, однако длина этого пути будет равна 10 - больше, чем у прямого пути из А в Е, поэтому изменения в наборе путей не производятся.

На рис. 6.8 (г) мы можем выбрать теперь либо путь из А в Е, либо путь из А в Е, проходящий через вершину В: оба они имеют длину 5. Какой из путей будет выбран при исполнении программы, зависит от способа хранения данных в ней. Мы же, встретившись с необходимостью добавить вершину, будем всегда выбирать вершину, метка которой первая в лексикографическом порядке.

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

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

На рис. 6.8 (е) видно, что путь в вершину В короче пути в вершину О. Поэтому мы добавляем к дереву вершину В и получаем ситуацию, изображенную на рис. 6.8 (ж).

Осталось добавить только вершину О, и в результате мы получаем дерево кратчайшего пути с рис. 6.8 (з). Длина кратчайшего пути из А в О равна 10. Вернувшись к рис. 6.5 (з), мы находим на нем еще один пример минимального остовного дерева, в котором путь между А и О не является кратчайшим: его длина равна 11.

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

4. Тестовый пример (вручную)

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

5. Содержательный (словесный) алгоритм

B) for i:= 2 to n do

D) for i:= 1 to л - 1 do begin

E) выбор из множества V\S такой вершины w,

что значение D[w] минимально;

F) добавить w к множеству S;

G) for каждая вершина v из множества V\S do

(8) D[v]:= min(D[v], D[w] + C[w, v] )

7. Реализация программы

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

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

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

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

Кроме стандартных функций из библиотек iostream.h, string.h, stdio.h, conio.h были использованы также следующие функции.

· word minim(word x, word y) - функция, которая возвращает минимальное из x и y.

· int min(int n) - функция, которая возвращает номер элемента массива l[i] минимальной «неотмеченной» длиной пути(flag[i]=0).