Алгоритмынахождениякратчайшихпутейвграфе

Государственное образовательное учреждение

Высшее профессиональное образование

Донской государственный технический университет кафедра ПОВТ и АС

Отчет по курсовой работе по курсу «Алгоритмы, построение и анализ»

на темы«Алгоритмы нахождения кратчайших путей в графе.»

Выполнил ст. гр. УСУ‐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,vV) вычисляют некоторые верхние ограничения 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), vV ориентированного графа при условии, что граф не содержит контуров отрицательной длины (n - количество вершин в графе). Исходными данными для этого алгоритма являются матрица весов дуг A[u,v].

На рисунке 1 приведен: (а) граф; (б) соответствующая ему матрица весов дуг; (в) результаты работы алгоритма Форда-Беллмана.

а б в

Рис. 1: Пример выполнения алгоритма Форда-Беллмана.

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

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

Даная задачу нужно рассматривать, как задачу оптимизации на графах. Она заключается в составлении программного кода на языке программирования Pascal, основываясь на алгоритме Форда-Беллмана, и её тестирования с ручном просчётом.

АЛГОРИТМИЗАЦИЯ.

Рис 2: Блок-схема.

Пояснения к блок-схеме.

1. Задание входных данных.

а) Пользователь вводит число вершин в графе. И в зависимости какое число выбрал пользователь, задается

Внимание, отключите Adblock

Вы посетили наш сайт со включенным блокировщиком рекламы!
Ссылка для скачивания станет доступной сразу после отключения Adblock!

Скачать