Алгоритм форда беллмана курсовая работа

непустое
множество
<#»792024.files/image029.gif»>

Шаг 1. Около первой строки матрицы M, слева от
матрицы, поставим числовую пометку «0» и такую же пометку проставим над первым
столбцом матрицы. Затем рассмотрим помеченную строку слева направо и всякий
раз, встречая клетку с числом, прибавим это число к пометке строки и сумму
проставим над столбцом, в котором эта клетка находится. Затем отразим пометки
столбцов относительно главной диагонали. Возникнут помеченные строки. С каждой
из помеченных строк проделаем то же самое: просмотрим помеченную строку слева
направо и всякий раз, встречая клетку с числом, прибавим это число к пометке
строки и сумму поставим в качестве пометки над столбцом, в котором эта клетка
стоит. При этом будем соблюдать принцип: «имеющуюся пометку не менять». Затем
пометки столбцов отразим относительно главной диагонали и с помеченными
строками вновь проделаем то же самое. И так далее, пока не окажутся помеченными
все строки и все столбцы.

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

Шаг 3. Теперь по пометкам можно построить
кратчайшие пути из первой вершины во все остальные. Фиксируем произвольную
вершину k (k = 2,3,…p) и опишем кратчайший путь из первой вершины в вершину
k. Во-первых, длина этого кратчайшего пути равна пометке л k , стоящей над
столбцом номер k. Во-вторых, предпоследняя вершина в кратчайшем пути из первой
вершины в вершину k находится так: в столбце номер k отыскиваем число, сумма
которого с пометкой строки, в которой оно расположено, равна л k. Пусть номер
строки, в которой найденное число оказалось, равен l. Тогда предпоследней
вершиной в кратчайшем пути из 1 в k будет вершина l. Вершину, которая
предшествует вершине l, надо отыскивать как предпоследнюю в кратчайшем пути из
1 в l и так далее.

Таблица 2.1. Обозначение элементов.

Обозначение
элементов математической модели

Наименование
элементов математической модели

1

G

Граф

2

V

Количество
вершин графа

3

E

Количество
ребер графа

3.     
Разработка структуры программы и алгоритмов программных модулей и их описание

Структура программы

Структура программы показана на рис. 3.1.

Рис. 3.1. Модульная структура программы.

Сопряжения модулей

Сопряжение модулей программы описана в таблице
3.1.

Таблица 3.1. Сопряжение модулей.

Номер

Вход

Выход

1

int
n, int s

bool

4.      Решение задачи на конкретном примере

Рассмотрим на контрольном примере решение задачи
с входным файлом “input.txt
. В входном файле будут содержаться количество вершин в графе и матрица
смежности. Бесконечность будет обозначаться 0.

Входной файл «input.txt»
имеет вид:

8

10 13 0 0 0 0 0

0 0 0 0 0 11 0

0 0 17 10 0 0 0

0 17 0 0 16 12 0

0 10 0 0 11 0 15

0 0 16 11 0 15 10

11 0 12 0 15 0 0

0 0 0 15 10 0 0

.        Считываем количество вершин.

.        Считываем и проверяем веса ребер: если
вес ребра больше 100000, или меньше -100000, или не цифра выводим ошибку, если
равна 0 приписываем значение 100000 (бесконечность).

.        Вводим начальную вершину и проверяем:
если меньше единицы, или больше количества вершин, или не цифра выводим ошибку
и просим повторить ввод.

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

Приведем пример. Пусть исходный взвешенный граф
дает следующую матрицу M:

Начнем расставлять пометки:

Проведем уменьшение пометок:

.        Выводим кратчайшие пути

→2: 10;

→3: 13;

→4: 30;

→5: 23;

→6: 34;

→7: 21;

→8: 38;

Структура данных

<Количество вершин>

<Веса ребер >

<Стартовая вершина >

Количество вершин не может превышать величины
заданной программистом (в нашем случае 1000) и быть меньше 2.

Значение стартовой вершины не может превышать
значения количества вершин и быть меньше нуля.

Описание массивов в программе приведено в
таблице 5.1.

Таблица 5.1. Обозначения и описания массивов

Имя
массива

Размерность
массива

Описание
массива

1

edge

Emax
— Максимальное количество ребер в графе

Для
хранения данных о ребрах

2

d

Vmax
— максимальное количество вершин в графе.

Для
хранения значений кратчайших путей

Описание переменных в программе приведено в
таблице 5.2.

Таблица 5.2. Описание переменных.

Имя
переменной

Тип
переменной

Описание
переменной

1

N

int

Количество
вершин

2

Vmax

int

Размер
массива или максимальное количество вершин

3

Emax

int

Максимальное
количество ребер

u,v

int

Вершины
ребра

5

success

bool

Используется
при проверки правильности ввода

6

i,j

int

Счетчики

7

W

int

Вес
ребра

8

E

Int

Количество
ребер

9

Start

Int

Стартовая
вершина

10

in, out

ifstrеam

Объекты
для работы с файлами

5.     
Программная реализация алгоритма решения задачи и ее описание

В программной реализации алгоритма на Microsoft
Visual Studio
2013 требуется включить следующие библиотеки:

«stdafx.h» — включаемый файл для
стандартных системных включаемых файлов или включаемых файлов для конкретного
проекта, которые часто используются, но не часто изменяются.

«iostream» — объектно-ориентированная
иерархия классов, где используется и множественное, и виртуальное наследование.
В ней реализована поддержка для файлового ввода/вывода данных встроенных типов.

В реализации программы также потребуются
нижеперечисленные функции и методы:- функция вывода в командную строку

cin — функция
считывания из командной строки.clear — функция очистки потока

_flushall — функция очистки буфера- функция
проверки правильности ввода

Программная реализация алгоритма представлена в
приложении A.

6.      Разработка системы тестов и отладка
программы

Тесты черного ящика

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

Таблица 7.1. Области входных/выходных данных
тестов программы

Входные
и выходные параметры

Допустимые
значения

Недопустимые
значения

Количество
вершин, n

2…Vmax (1)

<2 (2), >Vmax (3), не
цифра (4)

Вес
ребра, w

-100000…1000000 (5)

Не
цифра (6), <-100000 (7), >1000000 (8)

Стартовая
вершина, start

0…n (9)

<1 (10), >n (11), не
цифра (12)

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

Таблица 7.2. Тесты черного ящика для отладки
программы


теста

Входные
данные

Выходные
данные


ситуаций

1

2 5 6 4 2 2

4 0

1, 5, 9

2

1001 5 3 6 …

 Значение
введено неверно. Повторите ввод

3,
5, 9

3

1 6 35 …

Значение
введено неверно. Повторите ввод

2, 5, 9

4

Значение
введено неверно. Повторите ввод

4, 5, 9

5

3 5 1000000000 …

Значение
введено неверно. Повторите ввод

8, 1, 5, 9

6

5 6 -1000000000 …

Значение
введено неверно. Повторите ввод

7, 1, 5, 9

7

9 4 f x …

Значение
введено неверно. Повторите ввод

6, 1, 5, 9

8

2 6 3 5 8 3

Значение
введено неверно. Повторите ввод

11, 1, 5, 9

9

2 6 3 5 8 0

Значение
введено неверно. Повторите ввод

10, 1, 5, 9

10

2 6 3 5 8 0

Значение
введено неверно. Повторите ввод

12,
1, 5, 9

Тесты белого ящика

Разработанные тесты методом белого ящика по
критериям охвата основных путей выполнения алгоритма подпрограмм. В программе
имеются составные условия. Поэтому использован критерий комбинаторного покрытия
условий (см. таблицу 7.3).

Таблица 7.3. Комбинаторное покрытие условий
тестами черного ящика

Из таблицы 7.3 видно, что тесты черного ящика
обеспечивают полное комбинаторное покрытие всех ситуаций, поэтому нет необходимости
в тестах белого ящика.

Заключение

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

Ниже следуют пункты, рассмотренные в курсовой
работе.

)        Оформлялась содержательная часть задачи
нахождения кратчайших расстояний графа.

)        Разрабатывалась алгоритм решения
задачи.

)        Разрабатывались структуры программы и
алгоритмы программных модулей.

)        Решил задачу на контрольном примере.

)        Разрабатывался и описывался граф.

)        Исходя из разработанного алгоритма,
реализовалась программа.

)        Разрабатывались системы тестов в виде
черных и белых ящиков.

Алгоритм был реализован еа языке высокого уровня
С++. Отлаживалась программа в среде разработки Microsoft
Visual studio
2013.

Курсовая работа выполнена в соответствии с
требованиями в полном объеме.

Список литературы

1. Хохлов Д.Г. Основы технологии
модульного программирования.

Учебное пособие — Казань: КГТУ
(КАИ), 2003. 64 с.

.   Павловская Т.А. С/С++
Программирование на языке высокого уровня. Изд-во Питер, 2003. — 461 с.

3.      Белицкий Я. Энциклопедия
языка Си. М.: Мир, 1992.

.        Липский В. Комбинаторика
для программистов. М.: Мир, 1988.

5. Левитин А.В. Алгоритмы: ввдение в
разработку и анализ. / А. В. Левитин ; пер. с англ. под общ. ред. С.Г. Тригуб.
— М. : Издательский дом «Вильямс», 2006. — 576 с.

6.      Макконелл Дж. Основы
современных алгоритмов / Дж. Макконелл ; пер. с англ. под общ. ред. С.К. Ландо.
— М. : Издательство ЗАО РИЦ «Техносфера», 2004. — 368 с.

7. Ананий В. Левитин Глава 8.
Динамическое программирование:

Алгоритм Флойда поиска кратчайших
путей между всеми парами вершин // Глава 9. Жадные методы: Алгоритм Дейкстры //
Алгоритмы: введение в разработку и анализ = Introduction to The Design and
Analysis of Aigorithms. — М.: Вильямс , 2006. — С. 189-195, С. 349 — 353.

.   Томас Х. Кормен, Чарльз И.
Лейзерсон, Рональд Л. Ривест,

Клиффорд Штайн Алгоритмы: построение
и анализ = Introduction to Algorithms. — 2-е изд. — М.: Вильямс, 2006. — С.
1296.

.   https://ru.wikipedia.org

Приложение

Листинг программы

#include «stdafx.h»

#include <iostream>

#include «fstream»

#define inf 100000
//бесконечностьnamespace std;

// структура ребер

struct
Edges{

int
u,v,//вершины
ребра

w;//вес ребра

};

const
int Vmax
= 1000; // Максимальное количество вершин

const
int Emax
= Vmax*(Vmax
— 1) / 2; //Максимальное количестов ребер

int
i, j,//счетчики

e,//количество ребер

start;
//стартовая вершина

Edges
edge[Emax];
// создаем переменную типа Edges

int
d[Vmax];
//массив в котором будут храниться наикратчайшие пути

bool
success = false;
// для проверки правильности ввода

//алгоритм
Беллмана-Фордаbellman_ford(int n, int s)

{i, j;(i = 0; i<n; i++) d[i] =
inf;[s] = 0;(i = 0; i<n — 1; i++)(j = 0; j<e; j++)(d[edge[j].v] +
edge[j].w<d[edge[j].u])[edge[j].u] = d[edge[j].v] + edge[j].w;(i = 0;
i<n; i++) if (d[i] == inf)<< endl << start <<
«->» << i + 1 << «=» <<
«Нет»;cout << endl << start << «->»
<< i + 1 << «=» << d[i];

}

//Функция
ввода значений

bool vvod()

{in(«input.txt»);(!in) { <<
«Ошибка! Не удалось открыть файлn»;

return false;

}w;>> n; (!(in.good()
&& n<Vmax && n>1)) //проверка
правильности ввода

{

cout << «Ошибка(1)
чтения из файла!n»;

return false;

}

cout << «Количество
вершин: » <<n <<endl;

e = 0;

for (i = 0; i<n; i++)(j = 0;
j<n; j++)

{

in >> w;

if (!(in.good()
&& w<inf && w>-inf))
//проверка правильности ввода

{

cout << «Ошибка(2)
чтения из файла!n»;

return false;

}(w != 0)

{[e].v = i;[e].u = j;[e].w = w;++;

}

}<< «Стартовая вершина
> «;= false;
(!success) /*пока не
введем верное значение*/

{

cin >> start;

if (cin.good()
&& start <= n && start >0)
//проверка правильности ввода

{

success = true;

}

else

{

cout << «Значение
введено неверно. Повторите ввод» << endl;= false;

}.clear(); // очистка потока

_flushall();

}true;

}

//главная функцияmain()

{(LC_ALL, «Rus»);(!vvod())
goto end;<< «Список кратчайших путей:»;_ford(n, start —
1);:(«pause>>void»);

Блок-Схема

Похожие работы на — Алгоритм Беллмана—Форда

Реализация алгоритма Беллмана-Форда поиска кратчайших путей от заданной вершины

Автор:   •  Март 18, 2018  •  Курсовая работа  •  1,719 Слов (7 Страниц)  •  1,293 Просмотры

Страница 1 из 7

Реферат

Отчет 11 с., 2 рис., 1 табл., 3 источ., 1 прил.

ГРАФЫ, АЛГОРИТМ, ПРОГРАММА, КРАТЧАЙШИЙ ПУТЬ, ВЫЧИСЛЕНИЕ

Объектом исследования является ориентированный граф с взвешенными рёбрами.

Цель работы – реализация алгоритма Беллмана-Форда, посредством языка программирования C#.

В процессе работы проводилось тщательное изучение алгоритма Форда-Беллмана и некоторых основ языка C#.

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

Основные конструктивные и технико-эксплуатационные показатели: простота в использовании и доступность для любого уровня пользователей.

Степень внедрения – для учебных целей.

Эффективность программы определяется в простоте алгоритма и способностью быть наглядным примером для представления ориентированных графов.


Содержание

Введение        6

1 Постановка задачи        7

2 Схема основных алгоритмов        7

3 Аспекты реализации на языке C#        8

4 Руководство пользователя        8

5 Результаты тестирования        8

Заключение        9

Список использованных источников        10

Приложение А        11


Введение

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

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

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


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

Задача – реализовать алгоритм Беллмана-Форда поиска кратчайших путей от заданной вершины.

2 Схема основных алгоритмов

Пусть V – количество вершин в графе, S – начальная вершина, d – массив расстояний, A – массив весов рёбер.

Тогда схема алгоритмов имеет вид, представленный на рисунке 1.

[pic 1][pic 2][pic 3][pic 4]

[pic 5][pic 6][pic 7][pic 8][pic 9][pic 10][pic 11][pic 12][pic 13][pic 14][pic 15][pic 16][pic 17][pic 18][pic 19][pic 20][pic 21][pic 22][pic 23][pic 24][pic 25][pic 26][pic 27][pic 28][pic 29][pic 30][pic 31][pic 32][pic 33][pic 34][pic 35][pic 36][pic 37][pic 38][pic 39][pic 40][pic 41][pic 42][pic 43][pic 44][pic 45][pic 46][pic 47][pic 48][pic 49][pic 50][pic 51][pic 52][pic 53][pic 54][pic 55][pic 56][pic 57][pic 58][pic 59][pic 60][pic 61][pic 62][pic 63][pic 64][pic 65][pic 66][pic 67]

Рисунок 1 – Схема алгоритмов


3 Аспекты реализации на языке C#

В процессе реализации алгоритма было использовано следующее: функция случайного заполнения матрицы смежности в определенном диапазоне, оператор «try-catсh», а также алгоритм Беллмана-Форда [1].

4 Руководство пользователя

Программа разработана на Windows Form Application, что, несомненно, улучшает интерфейс и позволяет работать пользователям любого уровня [2]. Для того, чтобы вычислить кратчайший путь от какой-либо вершины, достаточно задать матрицу смежности и нажать кнопку «Вычислить». После чего программа выдаст результат, представленный в виде последовательности чисел.

Доступно только на Essays.club


< Программирование, компьютеры и кибернетика

Поиск на сайте math-solution.ru рефератов, курсовых, дипломных и контрольных работ, презентаций и т.д.

курсовая работа на тему:

Алгоритм Беллмана—Форда

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

Категория: Программирование, компьютеры и кибернетика
Предмет: Программирование на языке высокого уровня
Вид: курсовая работа

< Программирование, компьютеры и кибернетика

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *