Алгоритмынахождениякратчайшихпутейвграфе (стр. 1 из 2)
Государственное образовательное учреждение
Высшее профессиональное образование
Донской государственный технический университет кафедра ПОВТ и АС
Отчет по курсовой работе по курсу «Алгоритмы, построение и анализ»
на темы«Алгоритмы нахождения кратчайших путей в графе.»
Выполнил ст. гр. УСУ‐21
Герусов К.А.
Руководитель работы:
Горлова М.Ю.
Медведева Т.А.
Ростов‐на‐Дону 2010г.
СОДЕРЖАНИЕ.
Введение……………………………………………………………….…………………………………………………………………….. 3
Постановка задачи…………….……………………………….……………………………………………………………………….. 5
Алгоритмизация………………….………….…………………………………………………………………………………………… 6
Выполнение поставленной задачи…………....………………………………………………………………………………. 9
Ручной просчёт………….…………………………………………………………………………………………………….. 9
Тест программы………………………..……………………………………………………………………………………. 11
Код программы…………………….…….…………………………………………………………………………………………….. 13
Приложение……………………………………..……………………………………………………………………………………….. 16
Список литературы……………………………………………………………………………………………………………………. 18 ВВЕДЕНИЕ.
Граф - исключительно популярный объект, минимально удаленный как от своего целостного пространственного образа, так и от описания по всем правилам теории множеств. Всякий раз, когда с задачей удается связать граф, обсуждение резко упрощается и большие фрагменты словесного описания заменяются манипуляциями с картинками.
Ю.И.Манин.
Многосвязная структура характеризуется следующими свойствами: (1) каждый элемент структуры содержит произвольное число направленных связей с другими элементами (или ссылок на другие элементы); (2) с каждым элементом может связываться произвольное количество других элементов (каждый элемент может быть объектом ссылки произвольного количества других элементов); (3) каждая связь в структуре имеет не только направление, но и вес. Такую многосвязную структуру называют сетевой структурой или сетью. Заметим, что логически сеть эквивалентна взвешенному ориентированному графу общего вида, и поэтому вместо термина "сеть" часто употребляются термины "графовая структура", или даже просто "граф".
Особое значение сетевые структуры приобрели в системах искусственного интеллекта, в которых они адекватно отражают логику организации данных и сложные отношения, возникающие в таких системах между различными элементами данных. В этих системах сетевые структуры применяются для построения семантических сетей, фреймов и других логических конструкций, необходимых для представления знаний, образования понятий и осуществления логических выводов.
Кратчайшие пути в графе. Алгоритм Форда-Беллмана.
Мы взбираемся на вершину, откуда можем бросить гордый взгляд назад и оценить пройденный путь.
П.Буль.
Существует большое количество практических задач, сводящихся к поиску кратчайших путей в графе. К их числу можно отнести: поиск кратчайшего расстояния между городами; поиск пути передачи информации, обеспечивающего минимальную стоимость или минимальное время передачи, или максимальную надежность при распространении информации в разветвленной сети.
Исходными данными для поиска кратчайшего пути в графе является матрица весов дуг заданного ориентированного графа. Это означает, что каждой дуге (u,v)
E поставлено в соответствие некоторое вещественное число А(u,v), называемое весом данной дуги. Длину кратчайшего пути d(s,t) между вершинами s и t называют расстоянием от s до t (расстояние, определенное таким образом, может быть и отрицательным). Если не существует ни одного пути из s в t, то полагают d(s,t)=Ґ, где Ґ- некоторый символ.Большинство алгоритмов поиска расстояний между двумя фиксированными вершинами s и t включают в себя следующие действия: по данной матрице весов дуг A*u,v] (u,v
V) вычисляют некоторые верхние ограничения D*v+ на расстояние от s до всех вершин v. На каждом шаге, если D*v++A*u,v+<D*v+ оценку D*v+ улучшают: D*v+=D*u++A*u,v+. Процесс прекращается, когда дальнейшее улучшение ни одного из ограничений невозможно.Алгоритм Форда-Беллмана позволяет найти расстояние от источника до всех вершин D[v]=d(s,v), v
V ориентированного графа при условии, что граф не содержит контуров отрицательной длины (n - количество вершин в графе). Исходными данными для этого алгоритма являются матрица весов дуг A[u,v].На рисунке 1 приведен: (а) граф; (б) соответствующая ему матрица весов дуг; (в) результаты работы алгоритма Форда-Беллмана.
а б в
Рис. 1: Пример выполнения алгоритма Форда-Беллмана.
Приведенный алгоритм отыскания кратчайших путей в графах с отрицательными длинами дуг, принадлежащий Форду, Муру и Беллману, может служить одним из возможных способов обнаружения контуров отрицательной длины (или циклов в неориентированном графе).
ПОСТАНОВКА ЗАДАЧИ.
Даная задачу нужно рассматривать, как задачу оптимизации на графах. Она заключается в составлении программного кода на языке программирования Pascal, основываясь на алгоритме Форда-Беллмана, и её тестирования с ручном просчётом.
АЛГОРИТМИЗАЦИЯ.
Рис 2: Блок-схема.
Пояснения к блок-схеме.
1. Задание входных данных.
а) Пользователь вводит число вершин в графе. И в зависимости какое число выбрал пользователь, задается матрица смежности из соответствующего файла.
б) Программа предлагает ввести начальную вершину i дерева кратчайших путей.
в) Если в i-ой строке матрицы смежности только 0, то есть из вершины i не выходит ни одной дуги, значит, вершину i нельзя рассматривать как начальную и переходим к пункту б.
г) Вывод матрицы смежности на экран, в табличном виде.
2. Инициализация выходных данных (массивы: кратчайших путей – l и предков – ftr).
а) Если существует дуга (i,j), то выполняется пункт б, иначе пункт в.
б) Расстояние от i до j – вес дуги (i,j).
в) Расстояние от i до j – бесконечно велико.
г) Предком всех вершин графа становиться начальная вершина i.
3. Построение дерева кратчайших путей в графе.
а) Если существует дуга (c,j), то существует путь i->c->j.
б) Если весовая величина пути i->c->j меньше уже установленного расстояния от вершины i до j, то выполняется пункт в, иначе к пункту г.
в) Предком вершины j становится промежуточная вершина c, а расстояние от i до j сумма весов дуг пути i->c->j.
г) Для рассмотрения берётся следующая после вершина после вершины j – j+1.
д) Если все вершины занесены в дерево, то производится вывод на экран выходных данных, если нет, то происходит переход к пункту а.
ВЫПОЛНЕНИЕ ПОСТАВЛЕНОЙ ЗАДАЧИ.
Ручной просчет.
Даны 3 ориентированных графа G1(5,12), G2(4,7), G3(7,14), заданные матрицами смежности. Построить для этих графов деревья кратчайших путей.
Матрица смежности графа G1:0 6 7 7 2
0 0 3 8 -3
0 -1 0 0 -4
0 0 -3 0 9
0 0 7 0 0
Массив предков: ftr = (0, 3, 4, 1, 3).
Массив расстояний от 1-ой начальной вершины до остальных: l = (0, 3, 4, 7, 0).
Рис. 3: Граф G1.
Рис. 4: Дерево кратчайших путей для графа G1.
Матрица смежности графа G2:
0 7 0 5
4 0 3 -1
-2 0 0 -6
0 0 0 0
Массив предков: ftr = (0, 1, 2, 3).
Массив расстояний от 1-ой
начальной вершины до остальных: Рис. 5: Граф G2.
l = (0, 7, 10, 4).
Рис. 6: Дерево кратчайших путей для графа G2.
Матрица смежности графа G3:0 5 0 0 1 0 3
0 0 4 0 7 0 0
0 -4 0 0 -3 0 0
0 0 2 0 0 8 0
0 0 0 2 0 3 0
3 0 0 4 0 0 0
0 0 0 0 0 -1 0
Рис. 7: Граф G3.
Массив предков: ftr = (0, 3, 4, 5, 1, 7, 1).
Массив расстояний от 1-ой начальной вершины до остальных:
l=(0,1, 5, 3, 1, 2, 1).
Рис. 8: Дерево кратчайших путей для графа G3.
Тест программы.
Рис. 9: Выполнение программы для графа G1.
Рис. 10: Выполнение программы для графа G2.
Рис. 11: Выполнение программы для графа G3.
Рис. 12: Выполнение программы для графа G2.
В графе G2 есть вершина, из которой нельзя построить дерево кратчайших путей – это 4 вершина, так как из неё не выходят дуги. Программа проводит проверку на заданную пользователем вершину, в нашем случае 4, и проводит проверку и обнаруживает, что 4 не подходит. Далее программа вновь предлагает ввести номер вершины и для введенной 2 успешно вычисляет выходные массивы. Правильность данных можно проверить, сверив их с деревом кратчайших путей для графа G2 с начальной 2 вершиной на рисунке 13.