- Программная реализация
алгоритма решения задачи и ее описание
В программной реализации алгоритма
на Microsoft Visual Studio 2013
требуется включить следующие
библиотеки:
"stdafx.h" – включаемый файл
для стандартных системных включаемых
файлов или включаемых файлов для конкретного
проекта, которые часто используются,
но не часто изменяются.
"iostream" - объектно-ориентированная
иерархия классов, где используется и
множественное, и виртуальное наследование.
В ней реализована поддержка для файлового
ввода/вывода данных встроенных типов.
В реализации программы также
потребуются нижеперечисленные функции
и методы:
cout – функция вывода в командную
строку
cin – функция считывания из
командной строки
cin.clear – функция очистки потока
_flushall – функция очистки буфера
good – функция проверки правильности
ввода
Программная реализация алгоритма
представлена в приложении A.
- Разработка системы
тестов и отладка программы
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 видно, что тесты
черного ящика обеспечивают полное комбинаторное
покрытие всех ситуаций, поэтому нет необходимости
в тестах белого ящика.
ЗАКЛЮЧЕНИЕ
Алгоритм находит кратчайшие
пути от одной вершины графа до всех остальных.
Условие задачи — нахождение кратчайшего
пути между двумя станциями метро является
несколько другой задачей. Алгоритм использует
полный перебор всех вершин графа, что
приведет к большой потери времени и займет
больший объем памяти.
Ниже следуют пункты, рассмотренные
в курсовой работе.
- Оформлялась содержательная
часть задачи нахождения кратчайших расстояний графа.
- Разрабатывалась алгоритм решения
задачи.
- Разрабатывались структуры
программы и алгоритмы программных модулей.
- Решил задачу на контрольном
примере.
- Разрабатывался и описывался
граф.
- Исходя из разработанного алгоритма,
реализовалась программа.
- Разрабатывались системы тестов
в виде черных и белых ящиков.
Алгоритм был реализован еа
языке высокого уровня С++. Отлаживалась
программа в среде разработки Microsoft Visual
studio 2013.
Курсовая работа выполнена
в соответствии с требованиями в полном
объеме.
СПИСОК ЛИТЕРАТУРЫ
- Хохлов Д. Г. Основы технологии модульного
программирования.
Учебное пособие – Казань: КГТУ
(КАИ), 2003. 64 с.
- Павловская
Т. А. С/С++ Программирование на языке высокого уровня. Изд-во Питер, 2003. – 461 с.
- Белицкий Я. Энциклопедия языка Си. М.: Мир, 1992.
- Липский В. Комбинаторика для программистов. М.: Мир, 1988.
- Левитин А. В. Алгоритмы: ввдение в разработку и анализ. / А. В. Левитин ; пер. с англ. под общ. ред. С. Г. Тригуб. - М. : Издательский дом «Вильямс», 2006. - 576 с.
- Макконелл Дж. Основы современных алгоритмов / Дж. Макконелл ; пер. с англ. под общ. ред. С. К. Ландо. - М. : Издательство ЗАО РИЦ «Техносфера», 2004. - 368 с.
- Ананий В. Левитин Глава 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 //бесконечность
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
Блок-Схема