Задача поиска кратчайшего пути

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

ОГЛАВЛЕНИЕ

Введение

1. Общие сведения о графах

2. Постановка задачи

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

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

5. Алгоритм А*

6. Практическое применение

Заключение

Список использованной литературы

Приложения

ВВЕДЕНИЕ

«Задача поиска кратчайшего пути» (задача о минимальном пути, задача о дилижансе), в последнее время получила широкое распространение, благодаря своему применению для решения множества других задач.

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

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

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

1. ОБЩИЕ СВЕДЕНИЯ О ГРАФАХ

алгоритм задача путь граф

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

ВИДЫ ГРАФОВ И МЕТОДЫ ИХ ЗАДАНИЯ

Каждая пара вершин, имеющих связь, называется ребром графа. Ребра, имеющие направления, называются ориентированными. В связи с наличием/отсутствием ориентированных ребер в графе, графы делятся на:

· Ориентированные графы- содержат только ориентированные ребра;

· Неориентированные графы-содержат только неориентированные ребра;

· Смешанные графы - содержат как ориентированные ребра, так и неориентированные.

Ребро и вершина, которой оно принадлежит считаются инцидентными.

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

Ориентированный граф, с 6-ю вершинами

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

Матрица смежности

Матрица смежности графа G(V, E), где V-множество вершин, E- множество ребер данного графа это квадратная матрица A размера n, в которой значение элемента aij равно числу рёбер из i-й вершины графа в j-ю вершину.

Матрица смежности выглядит следующим образом:

Матрица смежности

Граф, соответствующий данной матрице

Матрица инцидентности

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

Матрица инцидентности

Граф, соответствующий данной матрице

Также существуют другие способы, но приведенные являются наиболее емкими и популярными.

МАРШРУТЫ, ПУТИ, СВЯЗНОСТЬ

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

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

Связность - это одно из наиболее простых свойств, которым может обладать граф.

Граф называется связным, если любая пара его вершин соединена простой цепью. Максимальный связный подграф графа G называется компонентой связности, или просто компонентой графа G. Таким образом, несвязный граф имеет по меньшей мере 2 компоненты.

Связный граф

На рисунке 4 приведен пример связного графа, с простыми цепями, соединяющими все вершины графа. Так, в данном графе вершины Aи Bсоединены простой цепью {A,B}, вершины B иD простой цепями {B,E,D}, {B,C,D}, {B,A,D}.

Простейшим примером несвязного графа является граф с изолированнойвершиной. Вершина называется изолированной, если она не имеет инцидентных ей ребер. Пример такого графа, с изолированной вершиной D приведен на рис. 5:

ВЕС И ДЛИНА ПУТИ

В некоторых задачах, ребрам ставят в соответствие числа, (обозначаемые ai ->ci) которые называютвесом (длиной)ребра.

Тогда граф G можно описать как 3 множества:

X- множество вершин, A - множество дуг, C - множество весов.

X = {x1,x2,x3…xi}

A = {a1,a2,a3…ai,}

C = {c1,c2,c3…ci,}

Несвязный граф

Взвешенный граф

Из рисунка видно, что вес ребра (4,5) равен 15. Вес пути принимается равным сумме весов входящих в него ребер. Вес пути A = (2,4,5), в данном случае равен сумме весов ребер (2,4) и (4,5) = 12+15 = 27.

2. ПОСТАНОВКА ЗАДАЧИ

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

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

Существуют различные постановки задачи о кратчайшем пути:

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

· Задача о кратчайшем пути между заданной парой вершин. Требуется найти кратчайший путь из заданной вершины u в заданную вершину v.

· Задача о кратчайшем пути между всеми парами вершин. Требуется найти кратчайший путь из каждой вершины u в каждую вершину v. Эту задачу тоже можно решить с помощью алгоритма, предназначенного для решения задачи об одной исходной вершине, однако обычно она решается быстрее.

Вес ребра также может заменяться на стоимость, скорость, расходы и.т.п., в зависимости от конкретной задачи.

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

Находит кратчайшее расстояние от одной из вершин графа до всех остальных, работает только для графов без рёбер отрицательного веса.

ЗАДАЧА

Дан взвешенный ориентированный граф G(V, E) без петель и дуг отрицательного веса. Найти кратчайшие пути от некоторой вершины a графа G до всех остальных вершин этого графа.

АЛГОРИТМ

0. Каждой вершине из V сопоставим метку -- минимальное известное расстояние от этой вершины до a. Алгоритм работает пошагово -- на каждом шаге он «посещает» одну вершину и пытается уменьшать метки. Работа алгоритма завершается, когда все вершины посещены.

1. Инициализация. Метка самой вершины a полагается равной 0, метки остальных вершин -- бесконечности. Это отражает то, что расстояния от a до других вершин пока неизвестны. Все вершины графа помечаются как не посещённые.

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

ПРИМЕР

В качестве примера возьмем неориентированный граф, и найдем минимальные расстояния от первой вершины до всех остальных:

При инициализации алгоритма, метка искомой вершины помечается 0, метки остальных вершин - бесконечностью:

Шаг №1: минимальную метку имеет вершина 1, её соседями являются 6, 3, 2. Рассмотрим их. Первый по очереди сосед вершины 1 -- вершина 2, потому что длина пути до неё минимальна. Длина пути в неё через вершину 1 равна сумме кратчайшего расстояния до вершины 1, значению её метки, и длины ребра, идущего из 1-й в 2-ю, то есть 0 + 7 = 7. Это меньше текущей метки вершины 2, бесконечности, поэтому новая метка 2-й вершины равна 7.



Аналогичную операцию проделываем с двумя другими соседями 1-й вершины -- 3-й и 6-й.

Все соседи вершины 1 проверены. Текущее минимальное расстояние до вершины 1 считается окончательным и пересмотру не подлежит. Вычеркнем её из графа, чтобы отметить, что эта вершина посещена.

Шаг №2. Снова находим «ближайшую» из не посещённых вершин. Это вершина 2 с меткой 7.

Соседями вершины 2 являются 1, 3 и 4, первая по очереди - уже вычеркнутая вершина 1, поэтому ее в рассмотрение не берем, вторая по очереди - вершина 3, путь до нее через вершину 2: 7 + 10 = 17, но 17 больше текущей метки этой вершины (9), поэтому метка не меняется. Также сосед 2-ой вершины - вершина 4, расстояние до нее через вершину 2: 7 + 15 = 22, 22 <, присваиваем вершине 4 метку 22.

Непросмотренных соседей вершины 2 не осталось, расстояние до нее можно считать окончательным, вершину помечаем как посещенную.



Шаг №3. Повторяем шаг алгоритма, выбрав вершину 3. После проверки всех её соседей получаем следующее:

Дальнейшие шаги. Повторяем шаг алгоритма для оставшихся вершин. Это будут вершины 6, 4 и 5, соответственно порядку.

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

До 2-ой - 7;

До 3-ей - 9;

До 4-ой - 20;

До 5-ой - 20;

До 6-ой - 11.

4. АЛГОРИТМ БЕЛЛМАНА-ФОРДА

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

ЗАДАЧА

Дан ориентированный или неориентированный граф G со взвешенными рёбрами. Требуется найти кратчайшие пути от выделенной вершины s до всех вершин графа.

АЛГОРИТМ

0. Перед началом работы алгоритма, для всех вершин, кроме стартовой, расстояние полагается равным бесконечности.

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

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

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

ПРИМЕР

Инициализация алгоритма. Метка истока приравнивается 0, остальные - бесконечности.



Шаг № 1. В цикле производится перебор всех ребер, начинаем с ребра 1-3. Для этого проверим не входит ли оно в путь более оптимальный, чем уже найденный. ?> 0 +6. Найден более короткий путь, метка вершины 3 меняется на значение 6 (проведена релаксация).

Шаг №2. Проверяем ребро 2-1. Для этого проверяем - не является ли оно частью более короткого пути, чем уже найденный. 0<? + 2.Релаксация не нужна, метка остается неизменной.

Шаг № 3. Проверяем ребро 3-2. Для этого проверяем - не является ли оно частью более короткого пути, чем уже найденный. ?> 6 + 48.Найден более короткий путь, метка вершины меняется на значение 54 (проведена релаксация).

Шаг 5-7. Снова проверяем ребра 1-3, 2-1, 3-2, в данном случае релаксация не требуется, минимальные расстояния уже найдены.

Шаг 8. Осталось проверить граф на наличие цикла отрицательного веса, достижимого из стартовой вершины. Для ребра 1-3 проверяется - может ли оно еще улучшить текущий найденный путь. Т.к. 1-3 не его не улучшает, оно не входит в цикл отрицательного веса.

Шаг 9-10. Аналогично ребру 1-3 проверяются ребра 2-1 и 3-2.

В графе нет циклов отрицательного веса, работа алгоритма закончена.

5. АЛГОРИТМ А*

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

ЗАДАЧА

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

АЛГОРИТМ

Добавляем стартовую клетку в открытый список;

Повторяем следующее:

Ищем в открытом списке клетку с наименьшей стоимостью F. Делаем ее текущей клеткой;

Помещаем ее в закрытый списоки удаляем с открытого;

Для каждой из соседних 8-ми клеток:

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

Если клетка еще не в открытом списке, то добавляем ее туда. Делаем текущую клетку родительской для этой клетки. Рассчитываем стоимости F, G и H клетки(пояснение в примере);

Если клетка уже в открытом списке, то проверяем, не дешевле ли будет путь в неё через эту клетку. Для сравнения используем стоимость G. Более низкая стоимость G указывает на то, что путь будет дешевле. Если это так, то меняем родителя клетки на текущую клетку и пересчитываем для нее стоимости G и F.

Останавливаемся если:

Добавили целевую клетку в открытый список, в этом случае путь найден;

Открытый список пуст и мы не дошли до целевой клетки. В этом случае путь отсутствует;

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

ПРИМЕР

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

Шаг №1. Начиная со стартовой клетки, помещаем ее в «открытый список» клеток, которые необходимо обработать. Ищем доступные клетки, граничащие с текущей, игнорируя непроходимые клетки. Добавляем найденные клетки в открытый список, указывая в качестве родителя текущую клетку. Удаляем стартовую клетку из открытого списка, и переносим в «закрытый список».

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

Шаг №2. Необходимо выбрать одну из клеток открытого списка для последующей обработки, в качестве таковой выбирается клетка с наименьшей стоимостью. Стоимость пути Fрассчитывается как сумма Gи H. F = G+H, где G-стоимость передвижения от стартовой точки A к данной клетке, по найденному пути. H - примерная стоимость передвижения от данной клетки к целевой (точке B). Стоимость Hрассчитывается с помощью эвристической (прогнозирующей) функции.

Как описано выше - Gэто стоимость передвижения со стартовой клетки, до текущей. В данном примере стоимость вертикальных и горизонтальных передвижения равняется 10, а диагональных - 14. Итак, G рассчитывается как стоимость пути к той точке, в которой мы сейчас находимся, плюс 10 в случае горизонтального расположения текущей клетки, относительно родительской, либо 14 в случае диагонального её расположения.

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

На следующе рисунке - в каждой клетке открытого списка записаны значения F, Gи H. F- в левом верхнем углу, G - в левом нижнем и H- в правом нижнем. У ортогональных клеток G равно 10, у диагональных - 14.



Расстояние H просчитано с помощью метода Манхеттена, из рисунка видно, что клетка справа от стартовой без учета преград находится за 3 клетки до конечной и имеет расстояние 30. (3 * 10 = 30). Клетка сверху - 5клеток и расстояние 50.

Шаг № 3. Для продолжения поиска выбираем клетку с наименьшей стоимостью F из всех клеток, находящихся в открытом списке. Удаляем её из открытого списка и добавляем в закрытый.

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

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

Из 9 клеток, исключая стартовую, добавленную в закрытый список, в открытом списке осталось 8, следующей клеткой является клетка, находящаяся справа от стартовой, т.к. у неё наименьший путь F (F = 40).

Сначала удаляем ее из открытого списка и добавляем в закрытый. Затем мы проверяем соседние клетки. Клетки, сразу справа от этой клетки - стены, поэтому их игнорируем. Клетка, прямо слева - стартовая клетка. Она находится в закрытом списке, поэтому ее тоже игнорируем.

Оставшиеся 4 клетки уже находятся в открытом списке, поэтому нужно проверить, не короче ли пути к этим клеткам, через текущую. Сравнение происходит по стоимости G. Давайте посмотрим на клетку, прямо под нашей выбранной клеткой. Ее стоимость G равна 14. При движении через к этой клетке через текущую её стоимость G будет равна 20 (10, стоимость G чтобы добраться к текущей клетке плюс 10 для движения вертикально вверх, к соседней клетке). G = 20>G = 14, потомуметка остается прежней.То есть более целесообразным будет движение по диагонали на одну клетку, чем движение на одну клетку по горизонтали, а потом одну по вертикали.

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

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

Клетка справа (стена) и клетка справа снизу пропускаются (справа снизу пропускается из-за того, что её не достичь без среза стены, зависит от условия задачи).

Остается еще 5 клеток. 2 клетки, находящиеся под текущей, еще не в открытом списке, потому их добавляем в открытый список и назначаем текущую клетку их "родителем". Из 3-х других клеток 2 уже находятся в закрытом списке (стартовая клетка и клетка, прямо над ней, на диаграмме обе подсвечены голубым цветом) их игнорируем. Последняя клетка, которая находится прямо слева от текущей, проверяется на длину пути по текущей клетке через эту клетку по стоимости G. Путь не станет короче, метка не меняется.Все соседние клетки рассмотрены, можно переходить к следующей.

Шаг 4 - N-1. Повторяем этот процесс до тех пор, пока не добавим целевую клетку в открытый список. К конечному шагу должна получиться схема похожая на приведенную на рисунке.

Можно заметить, что родительская клетка, для клетки находящейся на 2 клетки под стартовой изменилась. До этого ее родителем была клетка справа сверху, и стоимость была равна 28. После пересчета, оказалось, что до нее существует более короткий путь, равный 20, через вершину сверху (теперь туда направлен указатель).Стоимость F также изменилась.



Шаг N. Последним шагом является определение пути. Начиная поиск с конечной точки будем двигаться по указателям на родителя, постепенно доходя до начальной вершины, пройденные клетки и будут являться кратчайшим путем.

6. ПРАКТИЧЕСКОЕ ПРИМЕНЕНИЕ

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

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

Например протокол динамической маршрутизации «OSPF»разбивает процесс построения таблицы маршрутизации на 2 этапа.

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

Также алгоритм применяется при эвакуации населения из очагов бедствия. Оптимальные маршруты до пунктов сбора транспорта для каждой группы людей(дом,улица, школа и т.п)в штабе МЧС рассчитывает программа на основе алгоритма Дейкстры.

В области разработки игр широкое применение находит алгоритм А*, классическим примером его применения является игра «Lines», «ColorLines», в которой игроку необходимо составить в ряд несколько шаров, путь шара как раз рассчитывается с помощью этого алгоритма. Кроме этого А* применяется во многих играх жанра «RTS» (RealTimeStrategy), для расчете траектории движения юнитов, его модификации применяются в таких крупных проектах как «StarCraft2» и «Warcraft3».

ЗАКЛЮЧЕНИЕ

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

СПИСОК ИСПОЛЬЗОВАННОЙ ЛИТЕРАТУРЫ

1. Алексеев В.Е., Таланов В.А. - Графы. Модели вычислений. Структуры данных, Глава 3.4 Нахождение кратчайших путей в графе - Нижний Новгород, 2005;

2. Олифер В.Г. Олифер Н.А. - Основы компьютерных сетей - Питер, 2009;

3. «Глоссарий теории графов», http://ru.wikipedia.org/Глоссарий_теории_графов

4. «Задача о кратчайшем пути», http://ru.wikipedia.org/Задача_о_кратчайшем_пути;

5. «Алгоритм Дейкстры»,http://ru.wikipedia.org/Алгоритм_Дейкстры

ПРИЛОЖЕНИЯ

ИСХОДНЫЙ КОД РЕАЛИЗАЦИИ АЛГОРИТМА ДЕЙКСТРЫ

#include"stdafx.h"

#include<iostream>

usingnamespacestd;

constint V = 6;

voidDijkstra(intmatSize[V][V], intst)

{

int distance[V], count, index, i, u;

int m = st + 1;

bool visited[V];

for (i = 0; i<V; i++) {

distance[i] = INT_MAX;

visited[i] = false;

}

distance[st] = 0;

for (count = 0; count<V - 1; count++)

{

int min = INT_MAX;

for (i = 0; i<V; i++)

if (!visited[i] && distance[i] <= min)

{

min = distance[i]; index = i;

}

u = index;

visited[u] = true;

for (i = 0; i<V; i++)

if (!visited[i] &&matSize[u][i] && distance[u] != INT_MAX&&

distance[u] + matSize[u][i]<distance[i])

distance[i] = distance[u] + matSize[u][i];

}

cout<<"Стоимость пути из начальной вершины до остальных:\t\n";

for (i = 0; i<V; i++)

if (distance[i] != INT_MAX)

cout<< m <<" > "<<i + 1 <<" = "<< distance[i] <<endl;

else

cout<< m <<" > "<<i + 1 <<" = "<<"маршрутнедоступен"<<endl;

}

void main()

{

setlocale(LC_ALL, "Rus");

int start, matSize[V][V] =

{

{ 0, 1, 4, 0, 2, 0 },

{ 0, 0, 0, 9, 0, 0 },

{ 4, 0, 0, 7, 0, 0 },

{ 0, 9, 7, 0, 0, 2 },

{ 0, 0, 0, 0, 0, 8 },

{ 0, 0, 0, 0, 0, 0 }

};

cout<<"Начальнаявершина>> "; cin>> start;

Dijkstra(matSize, start - 1);

system("pause>>void");

}

ИСХОДНЫЙ КОД РЕАЛИЗАЦИИ АЛГОРИТМА БЕЛЛМАНА-ФОРДА

#include"stdafx.h"

#include<iostream>

#include<list>

#include<stack>

#include<limits.h>

usingnamespacestd;

classAdjListNode

{

int v;

intves;

public:

AdjListNode(int_v, int_w) { v = _v; ves = _w; }

intgetV() { return v; }

intgetves() { returnves; }

};

classGraph

{

int V;

list<AdjListNode> *adj;

public:

Graph(int V);

voidaddEdge(int u, int v, intves);

voidbellman_ford(intsrc);

};

Graph::Graph(intV)

{

this->V = V;

adj = newlist<AdjListNode>[V];

}

voidGraph::addEdge(intu, intv, intves)

{

AdjListNodenode(v, ves);

adj[u].push_back(node);

}

voidGraph::bellman_ford(intsrc)

{

int *dist = newint[V];

for (inti = 0; i< V; i++)

dist[i] = INT_MAX;

dist[src] = 0;

for (int u = 0; u < V; u++)

{

list<AdjListNode>::iteratori;

if (dist[u] != INT_MAX)

{

for (i = adj[u].begin(); i != adj[u].end(); ++i)

if (dist[i->getV()] >dist[u] + i->getves())

{

dist[i->getV()] = dist[u] + i->getves();

}

}

}

cout<<"Вершина\t\tРасстояние"<<endl;

for (inti = 0; i<V; i++)

{

cout<<i<<"\t\t"<<dist[i] <<"\t\t";

cout<<endl;

}

}

int main()

{

setlocale(LC_ALL, "rus");

Graphg(5);

g.addEdge(0, 1, -1);

g.addEdge(0, 2, 4);

g.addEdge(1, 2, 3);

g.addEdge(1, 3, 2);

g.addEdge(1, 4, 2);

g.addEdge(3, 2, 5);

g.addEdge(3, 1, 1);

g.addEdge(4, 3, -3);

int s = 1;

cout<<"Кратчайшие расстояния от источника "<< s <<" \n";

g.bellman_ford(s);

return 0;

}

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