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

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

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

ВВЕДЕНИЕ

Цель работы: изучить процедуры поиска кратчайшего пути на графе по алгоритму Дийкстры.

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

В общем, виде задача формулируется следующим образом. Пусть задан произвольный граф G(N,V), имеющий множество N вершин (узлов) и множество V ветвей. Структура графа задана матрицей длин ветвей А = ¦а_ij¦ размерности N. Длина отсутствующей ветви условно принимается равной бесконечности. На графе G выделяются две вершины: s - исток и t - сток. Необходимо определить путь от вершины s к вершине t в виде упорядоченной последовательности ветвей такой, чтобы сумма длин этих ветвей была наименьшей из всех возможных.

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

граф кратчайший путь маршрутизация

АЛГОРИТМ КРАТЧАЙШЕГО ПУТИ

В самом общем виде алгоритм кратчайшего пути, описанный в [1], содержит два этапа:

(1) начнём с того, что всем узлам припишем пометки вида (-, с(х)), где с(s)=0 и с(х)=? при х?s.

(2) попытаемся отыскать дугу (х,у), для которой

с(х) + а(х,у) < с(у) (1)

(причём здесь ? + а = ? ). Если такая дуга будет найдена, изменим пометку в узле у на ( х, с(х) + а(х,у)), т.е. произошло улучшение характеристики с(у) в сторону уменьшения. Новая пометка для узла у стала (х, с(у) ), которая означает, что если из узла s двигаться к узлу у через узел х и по ветви ху , то расстояние от s до у будет равно с(у).

Этап (2) повторяется до тех пор, пока будут находиться дуги (х,у), улучшающие характеристики с(у) какого-либо узла у. Если такую дугу больше найти нельзя, то процесс закончен, а совокупность пометок (х, с(у)) опишет дерево кратчайших путей из узла s в каждый узел у множества N.

Описанную процедуру проиллюстрируем на примере выбора кратчайшей автодороги из Ростова до Казани.

Пусть в некоторый момент времени сложилась ситуация, представленная на рис. 1. Здесь сплошными линиями показаны дороги, указанные в матрице длин ветвей А. Числами отмечены длины этих дорог в км. Пунктирными линиями показаны уже найденные длины путей от Ростова до 3-х городов. Эти пути могут содержать одну или более ветвей.

Рис. 1. Пример выбора кратчайшего пути на автодорогах

Предположим, что циклический процесс просмотра всех городов впервые подошёл к Казани. Значить пометка Казани равна (-, ?). Применим формулу (1) для нашего случая и для ветви С.Пб-Казань. Получим:

1900 + 1500 < ? .

Т.е. пометка Казани улучшилась и стала (С.Пб, 3400). Это означает, что если ехать из Ростова в Казань через С.Пб, то длина пути составит 3400км.

Применим формулу (1) для ветви Екб-Казань. Получим:

2700 + 1800 > 3400.

Т.е. пометка Казани не улучшается, остаётся прежней (С.Пб, 3400) и ездить в Казань через Екатеринбург мы не будем.

Применим формулу (1) для ветви Москва-Казань. Получим:

1200 + 900 < 3400.

Т.е. пометка Казани улучшилась и стала (Москва, 2100). Это означает, что если ехать из Ростова в Казань через Москву, то длина пути составит 2100км.

Как видим, алгоритм очень прост. Нужно только организовать циклический просмотр всех городов (от Абакана до Ярославля), а для каждого города - вложенный цикл с применением формулы (1) для всех входящих в него дорог (по конечным значениям соответствующего столбца матрицы А). Но у этого алгоритма есть существенный недостаток. Он очень длинен, особенно для сетей с большим числом узлов и ветвей. Если для схемы рис. 1 представить, что в какой-то момент улучшилась пометка Москвы и стала, например, (Воронеж, 1100), то начнут улучшаться все уже имеющиеся пометки, которые использовали пометку Москвы (Орёл, 1200). Улучшение пометки Казани может привести к возможности улучшить пометки Омска, Томска, Иркутска и многих других. Получается многократное прохождение одних и тех же узлов.

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

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

АЛГОРИТМ ДИЙКСТРЫ

Основная идея алгоритма Дейкстры (Dijkstra) состоит в том, что вводится понятие “окрашивания” фрагментов графа [2]. В начальный момент окрашена только вершина s (исток). Затем циклически при каждой процедуре шага 2 из нескольких смежных неокрашенных вершин выбирается вершина с минимальной величиной с(х) и производится окрашивание этой вершины и ветви, соединяющей эту вершину с ранее окрашенным фрагментом графа. Процесс окрашивания заканчивается, как только будет окрашена вершина t (сток). Алгоритм Дийкстры гарантирует, что для любой окрашенной вершины величина с(х) не может быть улучшена, т.е. уменьшена. Таким образом, исключается возможность многократного анализа одних и тех же вершин графа.

Формализованное описание алгоритма.

Шаг 1. Присвоить истоку s вес с(s) = 0, а всем остальным вершинам с(x) = ?. Присвоить переменной y значение s, т.е. принять y = s. Окрасить вершину s.

Шаг 2. Для каждой неокрашенной вершины х пересчитать величину с(x) следующим образом:

с(x) = min { с(x), с(y) + a(y,x) }, (2)

где x = 1-N, а N-общее число вершин в графе.

Окрасить дугу к выбранной вершине х и вершину х и указать для х направление к y. Присвоить y значение х, т.е. у = х.

Шаг 3. Если сток t оказался окрашенным, закончить процедуру, если нет - перейти к шагу 2.

Пример. Пусть задан 7-и узловой граф G(N,V), на котором выбраны исток s = 3 и сток t = 5 ( рис. 2).

Рис. 2. Исходный граф. 1-й этап. Исток s = 3, сток t = 5.

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

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

На 1-м этапе производится проверка 3-х вершин (1,4 и 6), непосредственно связанных с вершиной у = s = 3. По формуле (2) будет выбрана и окрашена вершина 1 и ветвь 31 (см. рис. 3). Величина у принимает значение вновь окрашенной вершины, т.е. у = 1.

Рис. 3. Окрашенный фрагмент после 2-го этапа.

На 2-м этапе проверяются вершины 2 и 4. Опять по формуле (2) выбирается и окрашивается вершина 4 и ветвь 14. Принимается у = 4.

Рис. 4. Окрашенный фрагмент после 3-го этапа.

На 3-м этапе проверяются вершины 2, 6 и 7. По формуле (2) выбирается и окрашивается вершина 7 и ветвь 47. Принимается у = 7.

Рис. 5. Окрашенный фрагмент после 4-го этапа.

На 4-м этапе проверяются вершины 2, 5 и 6. По формуле (2) выбирается и окрашивается вершина 2 и ветвь 72. Принимается у = 2.

Рис. 6. Окрашенный фрагмент после 5-го этапа.

На 5-м этапе проверяется единственная неокрашенная вершина 5, с которой связана вершина 2. Производится окрашивание вершины 5 и ветви 25. Поскольку окрашенным оказался сток t = 5, процесс поиска кратчайшего пути завершён.

Рис. 7. Окрашенный фрагмент после завершающего 6-го этапа.

Таблица окрашивания фрагментов графа

На графе рис. 7 кратчайший путь просматривается визуально. Однако, для машинной процедуры выбора пути необходимо пользоваться полученными в процессе поиска пометками. Чтение таблицы производится следующим образом: - в вершине 5 (сток t) пометка (2,7) означает, что путь от вершины 3 к вершине 5, проходящий через вершину 2, равен 7-и единицам;- пометка (7,5) в вершине 2 означает, что путь от вершины 3 к вершине 2, проходящий через вершину 7, равен 5-и единицам;

- пометка (4,4) в вершине 7 означает, что путь от вершины 3 к вершине 7, проходящий через вершину 4, равен 4-и единицам;

- пометка (1,3) в вершине 4 означает, что путь от вершины 3 к вершине 4, проходящий через вершину 1, равен 3-и единицам;

- пометка (3,1) в вершине 1 означает, что путь от вершины 3 к вершине 1, с которой вершина 3 связана непосредственно, равен 1-й единице.

Необходимо помнить, что в реальных ситуациях матрица длин ветвей, в отличие от рассмотренной в данном примере матрицы А, чаще всего бывает не симметрична. Это является следствием того, что не симметричными бывают информационные потоки, а, следовательно, и такие важные параметры, определяющие длины ветвей, как время ожидания пакетами в очереди или величина свободной пропускной способности канала. Поэтому найденный в нашем примере путь 3-1-4-7-2-5 длиной в 7 единиц это именно путь от вершины 3 к вершине 5.

Литература

1. Форд С., Фалкерсон Д. Потоки в сетях. Мир, М, 1966.

2. Шварц. Сети связи. Мир, М, 1992.

Размещено на Allbest.ru