Автор работы: Пользователь скрыл имя, 25 Марта 2012 в 23:09, курсовая работа
Целью данной курсовой работы является написание программы, реализующей алгоритм Форда-Беллмана. Алгоритм направлен на нахождение расстояния от источника до всех вершин и нахождение кратчайшего пути из S в T.
1. Введение 3
2. Постановка задачи 4
1. Представление кратчайших путей, релаксация……………………5
3. Алгоритм Форда-Беллмана 8
1. Перечень используемых величин и их назначение………………10
2. Входные и выходные данные, диапазон изменений……………..10
3. Блок-схема алгоритма...……………………………………………11
4. Заключение………………………………………………………………..13
5. Список используемой литературы………………………………………14
6. Приложение A. Инструкция к использованию программы..…………..15
7. Приложение B. Код программы………………………………………….17
Команда “open” предназначена для открытия файла с расширением “.fbk” в которой хранятся данные об орграфе. После ввода этой команды вам представится возможность ввода имени файла (без расширения).
При отсутствии файла или неправильной внутренней структуре файла программа выдаст сообщение об ошибке.
Команда “vvod” предназначена для непосредственного ввода орграфа. Для начала введите количество вершин от 4 до 50. Затем вам будет предложено выбрать между ориентированным графом и неориентированным. Каждый раз, на запрос ввода дуги, вы должны ввести три числа: начало, конец и вес дуги.
При ошибке ввода команд вам представиться возможность повторить ввод команд. Для этого на запрос о повторе поиска кратчайшего пути вы должны нажать клавишу “Y”, в противном случае вы выйдите из программы.
2. Ввод графа, начальной и конечной вершины.
После ввода команд на экране вы увидите весовую матрицу орграфа, с которым вы работаете. Вам будет предложено ввести начальную вершину. Если вы ввели существующую, для данного орграфа вершину, на экране появиться одномерная матрица с расстояниями до каждой вершины и вам представиться возможность ввода конечной вершины , в противном случае вам представиться возможность повторить ввод начальной вершины. Если в орграфе есть отрицательный контур программа выдаст сообщение об этом. Ввод конечной вершины аналогичен вводу начальной вершины. Если конечная вершина достижима из начальной, на экране появиться кратчайший путь, в противном случае сообщение об недостижимости.
Замечание: просьба вводить только числа, программа некорректно реагирует на символы в указании вершины.
3. Работа с файлами.
В программе вам представиться возможность работы с файлами. Для этого предусмотрена команда “open” для открытия файла. Для создания файла вы должны воспользоваться командой “vvod”, ввести орграф, пройти процедуру поиска кратчайшего пути, затем на запрос о сохранении файла нажать клавишу “Y” и ввести имя файла.
ПРИЛОЖЕНИЕ B.
Код программы.
#include <conio.h>
#include <iostream.h>
#include <fstream.h>
#include "windows.h"
#include <stdlib.h>
#include <string.h>
#define B 1000 //Бесконечность
int failopen(); //функция для открытия файла
int maxver; //количество вершин графа
//-------------Класс графа-------------------------
class Graph
{
private:
int **Ves; //матрица весов
int *Ras; //матрица расстояний
int *Fi; //Метки предыдущих вершин
public:
Graph(int MaxVer); //Конструктор
void Vess(int MaxVer,int gog); //Составление матрицы вечов
void Vess2(int MaxVer,int *mas);
void Display(int MaxVer); //Функция вывода графа
void FordBellman(int MaxVer); //Решение поставленной задачи
int Soh(int MaxVer); //функция сохранения
};
//-------------------Главная функция-----------------------
void main()
{
clrscr(); //очистка экрана
char kom[5]; //массив команды
int gog=0; //gog=0- орграф gog=1 - граф
char otv='a'; //вспомагательная переменная
while(otv) //цикл программы для многократного поиска кратч.пути
{
clrscr();
cout<<"\nВведите команду \n"; //ввод команды
cin>>kom;
if(strstr(kom,"open")) //проверка команды
{
failopen();
}
else if(strstr(kom,"vvod"))
{
char otvo='y';
cout<<"Введите число вершин от 4 до 50 : ";
cin>>maxver;
cout<<"Граф неориентированный? y-да"<<endl;
otvo=getch();
if(otvo=='y' || otv=='Y')
gog=1;
else gog=0;
if(maxver>3 && maxver<50)
{
Graph g(maxver);
g.Vess(maxver,gog);
g.Display(maxver);
cout<<"\nРешение : "<<endl;
g.FordBellman(maxver);
g.Soh(maxver);
}
}
cout<<"\nПовторить поиск кратчайшего пути? (y-да)"<<endl;
otv=getch();
if(otv =='y' || otv =='Y')
continue;
else
{
cout<<"Выход"<<endl;
getch();
break;
}
}
}
//-------------------Функция открытия файла---------------------
int failopen()
{
char name[8],fname[12];
cout<<"Введите название файла (не более 8 символов) : ";
cin>>name; //составление расширенного имени файла
strcpy(fname,name);
strcat(fname,".fbk");
ifstream openh; //поток входных файловых данных
openh.open(fname,ios::in);
if (!openh)
{
cout<<"\nФайл не существкет";
return 1;
}
else
{
int n;
openh>>n;
if(n>3 && n<50)
{
int *failmas=new int[n*n];
for(int j=0;j<n*n;j++)
openh>>failmas[j];
Graph g(n);
g.Vess2(n,failmas);
g.Display(n);
g.FordBellman(n);
}
else
cout<<"\nОшибка файла ";
}
return 0;
}
//--------------------------Ко
Graph::Graph(int MaxVer)
{
Ves = new int *[MaxVer]; //Создание мартицы весов
for (int i = 0; i < MaxVer; i++)
{
Ves[i] = new int [MaxVer];
}
Ras=new int[MaxVer]; //Создание матрицы расстояний
Fi=new int[MaxVer]; //То же с метками
}
//-----------------------Вывод графа-------------------------
void Graph::Display(int MaxVer)
{
cout<<"\nГраф который вы ввели : "<<endl;
for(int j=0;j<MaxVer;j++)
{
for(int k=0;k<MaxVer;k++)
{
if(Ves[j][k]>999)
cout<<'0'<<" ";
else if (Ves[j][k]>99)
cout<<Ves[j][k]<<" ";
else if(Ves[j][k]<100 && Ves[j][k]>9)
cout<<Ves[j][k]<<" ";
else if(Ves[j][k]<10 && Ves[j][k]>=0)
cout<<Ves[j][k]<<" ";
else if(Ves[j][k]>-10 && Ves[j][k]<0)
cout<<Ves[j][k]<<" ";
else if(Ves[j][k]<-9 && Ves[j][k]>-100)
cout<<Ves[j][k]<<" ";
else if(Ves[j][k]<-100)
cout<<Ves[j][k]<<" ";
}
cout<<endl;
}
}
//----------------------Сохран
int Graph::Soh(int MaxVer)
{
char otv, sname[8], fsname[12];
cout<<"\nСохранить граф? y-да"<<endl;
otv=getch();
if(otv =='y' || otv=='Y')
{
cout<<"\nВведите имя файла (не более 8 символов): ";
cin>>sname;
strcpy(fsname,sname);
strcat(fsname,".fbk");
ofstream sohran;
sohran.open(fsname,ios::out|
if (!sohran)
{
cout<<"\nОшибка";
return 1;
}
else
{
sohran<<MaxVer<<' ';
for(int j=0;j<MaxVer;j++)
for(int c=0;c<MaxVer;c++)
sohran<<Ves[j][c]<<' ';
}
sohran.close();
}
return 0;
}
//-----------------Определение матрицы весов2-------------------
void Graph::Vess2(int MaxVer,int *mas)
{
int k=0;
for(int j=0;j<MaxVer;j++)
for(int c=0;c<MaxVer;c++)
{
Ves[j][c]=mas[k];
k++;
}
}
//-------------------Определен
void Graph::Vess(int MaxVer,int gog)
{
for(int j=0;j<MaxVer;j++) //Сначала все вершины несоединены
for(int c=0;c<MaxVer;c++)
Ves[j][c]=B;
int n=0,k=0,v=0;
int potolok=MaxVer*MaxVer;
for(int i=0;i<potolok;i++)
{
cout<<"Введите дугу : ";
cin>>n;
if(n==0)break;
cin>>k>>v;
if(n<=0 || k<=0 || k>MaxVer || n>MaxVer)
cout<<" Вершины нумеруются от 1 до "<<MaxVer<<endl;
Ves[n-1][k-1]=v;
if(gog==1)
Ves[k-1][n-1]=v;
}
}
//---Функция реализующая алгоритм Форда-Беллмана---------------
void Graph::FordBellman(int MaxVer)
{
int S; //Начальная вершина
int T; //конечная вершина
int i,k,u,v,j,e,rev=1,otkn=0;
int mi=0;
while(mi<3)
{
mi++;
cout << "Введите начало : ";
cin>>S;
S--;