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

 

 

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

 

 

В программной реализации алгоритма на Microsoft Visual Studio 2013

требуется включить следующие библиотеки:

 

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

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

 

 

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

 

cout – функция вывода в командную строку

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

cin.clear – функция очистки потока

_flushall – функция очистки буфера

good – функция проверки правильности ввода

 

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

 

 

 

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

 

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

 

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

№ теста	Входные данные	Выходные данные	№ ситуаций
	2 5 6 4 2 2	4 0	1, 5, 9
	1001 5 3 6 …	Значение введено неверно. Повторите ввод	3, 5, 9
	1 6 35 …	Значение введено неверно. Повторите ввод	2, 5, 9
	G 6 4 …	Значение введено неверно. Повторите ввод	4, 5, 9
	3 5 1000000000 …	Значение введено неверно. Повторите ввод	8, 1, 5, 9
	5 6 -1000000000 …	Значение введено неверно. Повторите ввод	7, 1, 5, 9
	9 4 f\ x …	Значение введено неверно. Повторите ввод	6, 1, 5, 9
	2 6 3 5 8 3	Значение введено неверно. Повторите ввод	11, 1, 5, 9
	2 6 3 5 8 0	Значение введено неверно. Повторите ввод	10, 1, 5, 9
	2 6 3 5 8 0	Значение введено неверно. Повторите ввод	12, 1, 5, 9

 

 

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

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

 

 

 

 

 

 

 

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

Элементарные условия	Истина	Ложь
n<2	2	3, 4
n>Vmax	3	1
Start>n	11	9
Start<1	10	9

 

 

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

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

ЗАКЛЮЧЕНИЕ

 

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

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

1. Оформлялась содержательная часть задачи нахождения кратчайших расстояний графа.
2. Разрабатывалась алгоритм решения задачи.
3. Разрабатывались структуры программы и алгоритмы программных модулей.
4. Решил задачу на контрольном примере.
5. Разрабатывался и описывался граф.
6. Исходя из разработанного алгоритма, реализовалась программа.
7. Разрабатывались системы тестов в виде черных и белых ящиков.

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

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

 

 

 

 

 

 

 

 

 

 

 

 

 

СПИСОК ЛИТЕРАТУРЫ

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

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

2. Павловская Т. А. С/С++ Программирование на языке высокого уровня. Изд-во Питер, 2003. – 461 с.
3. Белицкий Я. Энциклопедия языка Си. М.: Мир, 1992.
4. Липский В. Комбинаторика для программистов. М.: Мир, 1988.
5. Левитин А. В. Алгоритмы: ввдение в разработку и анализ. / А. В. Левитин ; пер. с англ. под общ. ред. С. Г. Тригуб. - М. : Издательский дом «Вильямс», 2006. - 576 с.
6. Макконелл Дж. Основы современных алгоритмов / Дж. Макконелл ; пер. с англ. под общ. ред. С. К. Ландо. - М. : Издательство ЗАО РИЦ «Техносфера», 2004. - 368 с.
7. Ананий В. Левитин Глава 8. Динамическое программирование:

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

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

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

7. https://ru.wikipedia.org

 

 

 

 

 

 

 

 

 

ПРИЛОЖЕНИЯ

 

Приложение А

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

 

#include "stdafx.h"

#include <iostream>

#include "fstream"

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

using namespace std;

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

struct Edges{

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

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

};

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

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

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

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

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

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

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

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

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

 

//алгоритм Беллмана-Форда

void bellman_ford(int n, int s)

{

int i, j;

 

for (i = 0; i<n; i++) d[i] = inf;

d[s] = 0;

 

for (i = 0; i<n - 1; i++)

for (j = 0; j<e; j++)

if (d[edge[j].v] + edge[j].w<d[edge[j].u])

d[edge[j].u] = d[edge[j].v] + edge[j].w;

 

for (i = 0; i<n; i++) if (d[i] == inf)

cout << endl << start << "->" << i + 1 << "=" << "Нет";

else cout << endl << start << "->" << i + 1 << "=" << d[i];

}

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

bool vvod()

{

ifstream in("input.txt");

if (!in) {

cout << "Ошибка! Не удалось открыть файл\n";

return false;

}

int w;

 

 

in >> n;

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

{

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

return false;

}

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

 

 

e = 0;

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

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

{

 

 

 

in >> w;

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

{

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

return false;

}

 

 

if (w != 0)

{

edge[e].v = i;

edge[e].u = j;

edge[e].w = w;

e++;

}

}

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

success = false;

while (!success) /*пока не введем верное значение*/

{

 

cin >> start;

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

{

 

success = true;

}

else

{

cout << "Значение введено неверно. Повторите ввод" << endl;

success = false;

}

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

_flushall();

}

 

return true;

}

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

void main()

{

setlocale(LC_ALL, "Rus");

if (!vvod()) goto end;

cout << "Список кратчайших путей:";

bellman_ford(n, start - 1);

end:

system("pause>>void");

 

Приложение B

 

Блок-Схема