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

№

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

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

1

G

Граф

2

V

непустое множество <#"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. Обозначение элементов.

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

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

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

1

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

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

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

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

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. Обозначения и описания массивов

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Разработанные тесты методом белого ящика по критериям охвата основных путей выполнения алгоритма подпрограмм. В программе имеются составные условия. Поэтому использован критерий комбинаторного покрытия условий (см. таблицу 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");

Блок-Схема

© 2003 - 2022 «Библиофонд»

Обратная связь

Пользовательское соглашение

Политика конфиденциальности

Полная версия

Помощь по учебным работам

Консультация по курсовой работе

Консультация по дипломной работе ВКР

Консультация по реферату

Консультация по отчетам о практике