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

Алгоритмы поиска маршрута с наименьшей стоимостью в сетях с коммутацией пакетов и объединенных сетях. Алгоритм Дейкстры, Беллмана-Форда. Расчет пути с минимальным количеством переходов. Преобразование схемы в неориентированный невзвешанный граф.

Рубрика Математика
Вид контрольная работа
Язык русский
Дата добавления 12.06.2013
Размер файла 1,1 M

Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже

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

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

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

Введение

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

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

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

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

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

Большинство алгоритмов поиска маршрута с наименьшей стоимостью, применяющихся в сетях с коммутацией пакетов и объединенных сетях, представляют собой вариации одного из двух общих алгоритмов, известных как алгоритм Дейкстры (Dijkstra) и алгоритм Беллмана - Форда (Bellman - Ford). В этом разделе обсуждаются оба алгоритма.

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

Алгоритм Дейкстры может быть сформулирован следующим образом. Алгоритм находит кратчайшие пути от данной вершины-источника до всех остальных вершин, перебирая пути в порядке увеличения их длин. Работа алгоритма проходит поэтапно. К k-му шагу алгоритм находит k кратчайших (с наименьшей стоимостью) путей к k вершинам, ближайшим к вершине-источнику. Эти вершины образуют множество Т. На шаге (k + 1) к множеству Т добавляется вершина, ближайшая к вершине-источнику среди вершин, не входящих во множество Т. При добавлении каждой новой вершины к множеству Т определяется путь к ней от источника. Формально этот алгоритм может быть определен следующим образом. Введем обозначения:

* N - множество вершин сети:

* s - вершина-источник;

* Т - множество вершин, уже обработанных алгоритмом:

* Дерево - связующее дерево для вершин, принадлежащих множеству Т, включая ребра, входящие в пути с наименьшей стоимостью от вершины s до каждой вершины множества Т:

* w (i.j) - стоимость линии от вершины i до вершины j, причем

w (i. j) = 0 или w (i j) = , если две вершины не соединены напрямую, и

w (i. j) 0, если две вершины соединены напрямую;

* L(n) - минимальная стоимость пути от вершины s до вершины n, известного на данный момент алгоритму (по завершении работы алгоритма это минимальная стоимость пути от вершины s до вершины n).

Алгоритм состоит из трех шагов. Шаги 2 и 3 повторяются до тех пор. пока множество Т не совпадет с множеством N. Это значит, что шаги 2 и 3 повторяются, пока для всех вершин сети не будут найдены окончательные пути.

1. Инициализация.

Т=Дерево = {s}, то есть множество исследованных вершин состоит пока что только из вершины-источника.

L(n) = w (s, n) для n s, то есть стоимости начальных путей к соседним вершинам представляют собой просто стоимости линий связи.

2. Получить следующую вершину.

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

Добавить вершину х к множеству Т и к дереву; добавить к дереву ребро, инцидентное вершине х, составляющее компонент пути L(x) с минимальной стоимостью, то есть последний ретрансляционный участок пути.

3. Обновить путь с минимальной стоимостью.

L(n) = min [L(n), L(x) + w (x, n)] для всех n T.

Если последняя величина минимальна, то с этого момента путь от вершины до вершины n представляет собой конкатенацию пути от вершины s до вершины х и пути от вершины х до вершины n.

Алгоритм завершает работу, когда все вершины добавлены к множеству Т. Таким образом, для работы алгоритма требуется |V| итераций. К моменту окончания работы алгоритма значение L(x), поставленное в соответствие каждой вершине х представляет собой минимальную стоимость (длину) пути от вершины s до вершины х. Кроме того, Дерево представляет собой связующее дерево исходного ориентированного графа, определяющее пути с минимальной стоимостью от вершины s до всех остальных вершин.

На каждой итерации при выполнении шагов 2 и 3 к множеству Т добавляется одна новая вершина, а также находится путь с минимальной стоимостью вершины s до этой вершины. Другими словами, на каждой итерации к множеству добавляется вершина х, а значение L(x) на этот момент времени представляет собой минимальную стоимость пути от вершины s до вершины х. Более того, путь с минимальной стоимостью определяется уникальным путем от вершины s, вершины х во множестве Т. Этот путь проходит только по вершинам, принадлежащим множеству Т. Чтобы понять это, рассмотрим следующую цепочку рассуждений. Вершина х, добавляемая на первой итерации, должна быть смежной с вершиной и не должно существовать другого пути к вершине х с меньшей стоимостью. Если вершина х не является смежной с вершиной s, тогда должна существовать другая вершина, смежная с вершиной s, представляющая собой первый транзитный участок пути с минимальной стоимостью к вершине х. В этом случае при выборе вершины, добавляемой к множеству Т, предпочтение будет отдано этой вершине, а не вершине х. Если вершина х является смежной с вершиной s, но путь s-х не является путем с наименьшей стоимостью от вершины s до вершины х, то это значит, что существует другая смежная с вершиной s вершина у, находящаяся на пути с минимальной стоимостью, и при выборе добавляемой к множеству Т вершины предпочтение будет отдано вершине у, а не вершине х. После выполнения k итераций во множество Т войдут k вершин и будет найден путь с минимальной стоимостью от вершины s до каждой из этих вершин. Теперь рассмотрим все возможные пути от вершины s до вершин, не входящих во множество Т. Среди этих путей существует один путь с минимальной стоимостью, проходящий исключительно по вершинам, принадлежащим множеству Т, заканчивающийся линией, непосредственно связывающей некую вершину множества Т с вершиной, не принадлежащей множеству Т. Эта вершина добавляется к множеству Т, а соответствующий путь считается путем с наименьшей стоимостью к данной вершине.

Исходная матрица смежности:

V1

V2

V3

V4

V5

V6

V1

V2

V3

V4

V5

V6

Построим исходный граф:

Рис. 1

Путь

Расстояние

Длина

V1V6

1

8

V1V2V6

2

13

V1V5 V3 V2 V6

4

14

V1V5 V4 V3 V2 V6

5

21

Таблица 1

Т

L(2)

Путь

L(3)

Путь

L(4)

Путь

L(5)

Путь

L(6)

Путь

1

8

1-2

-

-

1

1-5

8

1-6

2

8

9

1-2

1-6-2

-

-

1

1-5

8

1-6

3

8

9

1-2

1-6-2

15

16

1-2-3

1-6-2-3

-

1

1-5

8

13

1-6

1-2-6

4

8

9

1-2

1-6-2

15

16

1-2-3

1-6-2-3

21

20

1-6-2-3-4

1-2-3-4

1

21

22

1-5

1-2-3-5

1-6-2-3-5

8

13

1-6

1-2-6

5

8

9

1-2

1-6-2

15

16

1-2-3

1-6-2-3

21

20

1-6-2-3-4

1-2-3-4

1

21

22

27

28

1-5

1-2-3-5

1-6-2-3-5

1-2-3-4-5

1-6-2-3-4-5

8

13

1-6

1-2-6

6

8

9

9

16

1-2

1-6-2

1-5-3-2

1-5-4-3-2

15

16

5

12

1-2-3

1-6-2-3

1-5-3

1-5-4-3

21

20

5

10

1-6-2-3-4

1-2-3-4

1-5-4

1-5-3-4

1

21

22

27

28

1-5

1-2-3-5

1-6-2-3-5

1-2-3-4-5

1-6-2-3-4-5

8

13

14

21

1-6

1-2-6

1-5-3-2-6

1-5-4-3-2-6

Рис. 2

Рис. 3

Рис. 4

Рис. 5

Рис. 6

Рис. 7

2. Алгоритм Беллмана-Форда

Алгоритм Беллмана - Форда может быть сформулирован следующим образом. Требуется найти кратчайшие пути от заданной вершины при условии, что эти пути состоят максимум из одного ребра, затем найти кратчайшие пути при условии, что эти пути состоят максимум из двух ребер, и т.д. Этот алгоритм также работает поэтапно, формально он может быть определен следующим образом. Введем обозначения:

* s - вершина-источник;

* w (i, j) - стоимость линии от вершины i до вершины j, причем

w (i, j) = 0 или w(ij) =, если две вершины не соединены напрямую, и w (i.j) 0, если две вершины соединены напрямую;

* h - максимальное количество ребер в пути на текущем шаге алгоритма;

* Lh(n) - минимальная стоимость пути от вершины s до вершины n при условии, что этот путь состоит не более чем из h ребер.

Алгоритм состоит двух шагов. Шаг 2 повторяется до тех пор, пока стоимости путей не перестанут изменяться.

1. Инициализация:

L0(n) = для всех n s,

Lh(s) = 0 для всех h.

2. Обновление.

Для каждого последовательного h 0 и для каждого n s вычислить

Соединить вершину n с предыдущей вершиной j, для которой находится минимальное значение, и удалить любое соединение вершины n с предыдущей вершиной, образованное на более ранней итерации. Путь от вершины s до вершины n заканчивается линией связи от вершины j до вершины n.

При h = К для каждой вершины-получателя n алгоритм сравнивает потенциальный путь от вершины s до вершины n длиной К + 1 с путем, существовавшим к концу предыдущей итерации. Если предыдущий более короткий путь обладает меньшей стоимостью, то он сохраняется. В противном случае сохраняется новый путь от вершины s до вершины n длиной К + 1. Этот путь состоит из пути длиной К от вершины К до некоей вершины j и прямого участка от вершины j до вершины n. В этом случае используемый путь от вершины s до вершины j представляет собой путь, состоящий из К ретрансляционных участков, найденный на предыдущей итерации. По завершении работы алгоритма вычисляется связующее дерево графа.

Таблица 2

h

L(2)

Путь

L(3)

Путь

L(4)

Путь

L(5)

Путь

L(6)

Путь

0

-

-

-

-

-

1

8

1-2

-

-

1

1-5

8

1-6

2

8

9

1-2

1-6-2

5

15

1-5-3

1-2-3

5

1-5-4

1

1-5

8

13

1-6

1-2-6

3

8

9

9

1-2

1-6-2

1-5-3-2

5

15

16

12

1-5-3

1-2-3

1-6-2-3

1-5-4-3

5

10

20

1-5-4

1-5-3-4

1-2-3-4

1

21

1-5

1-2-3-5

8

13

1-6

1-2-6

4

8

9

9

16

1-2

1-6-2

1-5-3-2

1-5-4-3-2

5

15

16

12

1-5-3

1-2-3

1-6-2-3

1-5-4-3

5

10

20

21

1-5-4

1-5-3-4

1-2-3-4

1-6-2-3-4

1

21

22

27

1-5

1-2-3-5

1-6-2-3-5

1-2-3-4-5

8

13

14

1-6

1-2-6

1-5-3-2-6

5

8

9

9

16

1-2

1-6-2

1-5-3-2

1-5-4-3-2

5

15

16

12

1-5-3

1-2-3

1-6-2-3

1-5-4-3

5

10

20

21

1-5-4

1-5-3-4

1-2-3-4

1-6-2-3-4

1

21

22

27

28

1-5

1-2-3-5

1-6-2-3-5

1-2-3-4-5

1-6-2-3-4-5

8

13

14

21

1-6

1-2-6

1-5-3-2-6

1-5-4-3-2-6

Рис. 8

Рис. 9

Рис. 10

Рис. 11

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

Рис. 12

Рис. 13

3. Расчет пути с минимальным количеством переходов

Преобразуем исходную схему в неориентированный невзвешанный граф. В итоге получим граф:

V1

V2

V3

V4

V5

V6

V1

V2

V3

V4

V5

V6

Рис. 14

Е=8

Произведем поиск кратчайшего маршрута по алгоритму Дейкстры.

Таблица 3

Т

L(2)

Путь

L(3)

Путь

L(4)

Путь

L(5)

Путь

L(6)

Путь

1

1-2

-

-

1

1-5

1

1-6

1

2

1-2

1-6-2

-

-

1

1-5

1

1-6

1

2

1-2

1-6-2

2

3

1-2-3

1-6-2-3

-

1

1-5

1

2

1-6

1-2-6

1

2

1-2

1-6-2

2

3

1-2-3

1-6-2-3

4

3

1-6-2-3-4

1-2-3-4

1

3

4

1-5

1-2-3-5

1-6-2-3-5

1

2

1-6

1-2-6

1

2

1-2

1-6-2

2

3

1-2-3

1-6-2-3

4

3

1-6-2-3-4

1-2-3-4

1

3

4

4

5

1-5

1-2-3-5

1-6-2-3-5

1-2-3-4-5

1-6-2-3-4-5

1

2

1-6

1-2-6

1

2

3

4

1-2

1-6-2

1-5-3-2

1-5-4-3-2

2

3

2

3

1-2-3

1-6-2-3

1-5-3

1-5-4-3

4

3

2

3

1-6-2-3-4

1-2-3-4

1-5-4

1-5-3-4

1

3

4

4

5

1-5

1-2-3-5

1-6-2-3-5

1-2-3-4-5

1-6-2-3-4-5

1

2

4

5

1-6

1-2-6

1-5-3-2-6

1-5-4-3-2-6

Выводы

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

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

...

Подобные документы

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

    методичка [29,4 M], добавлен 07.06.2009

  • Основные понятия теории графов. Матричные способы задания графов. Выбор алгоритма Форда–Бэллмана для решения задачи поиска минимальных путей (маршрутов) в любую достижимую вершину нагруженного орграфа. Способы выделения пути с наименьшим числом дуг.

    курсовая работа [109,1 K], добавлен 22.01.2016

  • Метод Форда-Беллмана для нахождения расстояния от источника до всех вершин графа. Алгоритмы поиска расстояний и отыскания кратчайших путей в графах. Блочно-диагональный вид и матрица в исследовании системы булевых функций и самодвойственной функции.

    курсовая работа [192,1 K], добавлен 10.10.2011

  • Эйлеровы цепи и циклы, теоремы. Алгоритм построения эйлерова цикла. Обоснование алгоритма. Нахождение кратчайших путей в графе. Алгоритм Форда отыскания кратчайшего пути. Задача отыскания кратчайших расстояний между всеми парами вершин. Алгоритм Флойда.

    реферат [108,4 K], добавлен 01.12.2008

  • Потоки в сетях, структура и принципы формирования алгоритма Форда-Фалкерсона, особенности его реализации программным методом. Минимальные остовные деревья. Алгоритм Борувки: понятие и назначение, сферы и специфика практического использования, реализация.

    курсовая работа [311,3 K], добавлен 15.06.2015

  • Понятие и содержание теории графов. Правила построения сетевых графиков и требования к ним. Сетевое планирование в условиях неопределенности. Теория принятия решений, используемые алгоритмы и основные принципы. Пример применения алгоритма Дейкстры.

    курсовая работа [1,0 M], добавлен 26.09.2013

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

    курсовая работа [466,3 K], добавлен 28.04.2011

  • Теория графов как математический аппарат для решения задач. Характеристика теории графов. Критерий существования обхода всех ребер графа без повторений, полученный Л. Эйлером при решении задачи о Кенигсбергских мостах. Алгоритм на графах Дейкстры.

    контрольная работа [466,3 K], добавлен 11.03.2011

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

    реферат [131,8 K], добавлен 11.11.2008

  • Поиск кратчайших путей для пар вершин взвешенного ориентированного графа с весовой функцией. Включение матрицы в алгоритм Флойда, содержащую вершину, полученную при нахождении кратчайшего пути. Матрица, которая содержит длины путей из вершины в вершину.

    презентация [36,1 K], добавлен 16.09.2013

  • Основные понятия и свойства эйлеровых и гамильтоновых цепей и циклов в теории графов. Изучение алгоритма Дейкстры и Флойда для нахождения кратчайших путей в графе. Оценки для числа ребер с компонентами связанности. Головоломка "Кенигзберзьких мостов".

    курсовая работа [2,4 M], добавлен 08.10.2014

  • История слова "алгоритм", понятие, свойства, виды. Алгоритм Евклида, решето Эратосфена; математические алгоритмы при действии с числами и решении уравнений. Требования к алгоритмам: формализация входных данных, память, дискретность, детерминированность.

    реферат [1,1 M], добавлен 14.05.2015

  • Основные понятия теории графов. Содержание метода Дейкстры нахождения расстояния от источника до всех остальных вершин в графе с неотрицательными весами дуг. Программная реализация исследуемого алгоритма. Построение матриц смежности и инцидентности.

    курсовая работа [228,5 K], добавлен 30.01.2012

  • Алгоритм перехода к каноническому виду стандартной формы ЗЛП. Симплексные преобразования при изменении базисных переменных. Графический способ упорядочения вершин. Расчет параметров сетевого графика. Устойчивость решений ЗЛП при изменении параметров.

    учебное пособие [161,1 K], добавлен 14.07.2011

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

    курсовая работа [951,4 K], добавлен 22.01.2014

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

    курсовая работа [625,4 K], добавлен 30.09.2014

  • Постановка задачи коммивояжера и основные алгоритмы решения. Маршруты и пути. Понятия транспортной сети. Понятие увеличивающая дуга, цепь, разрез. Алгоритм Флойда-Уоршелл. Решение задачи аналитическим методом. Создание приложения для решения задачи.

    курсовая работа [541,3 K], добавлен 08.10.2015

  • Необхідні поняття теорії графів. Задача про максимальний потік. Алгоритм Форда знаходження максимального потоку. Модифікація алгоритму Форда розв’язання задачі максимізації кількості призначень у задачах розподілу. Результати числового експерименту.

    курсовая работа [499,9 K], добавлен 18.12.2013

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

    курсовая работа [495,4 K], добавлен 19.09.2011

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

    контрольная работа [378,6 K], добавлен 10.02.2009

Работы в архивах красиво оформлены согласно требованиям ВУЗов и содержат рисунки, диаграммы, формулы и т.д.
PPT, PPTX и PDF-файлы представлены только в архивах.
Рекомендуем скачать работу.