Порівняння алгоритмів
Для порівняння швидкості роботи
алгоритмів було розроблено генератор
графів. Генератор створює матрицю
суміжності, розмірності
,
деV – кількість
вершин графа. Та випадковим чином
розставляє на ній 1. Було вирішено
використовувати неорієнтовані прості
графи, тобто графи без паралельних ребер
та петель, ребра не мають напрямку.
Матриця суміжності набуває такого
вигляду: вона симетрична відносно
головної діагоналі, а головна діагональ
заповнена лише 0.
Приклад:
Граф, представлений даною матрицею суміжності містить 5 вершин і 7 ребер.
Оскільки графи задаються випадковим чином, ми будемо аналізувати середній час для пошуку на 25 випадкових графах однієї розмірності.
Лістинг програми
#include <iostream>
#include <time.h>
#include <conio.h>
using namespace std;
const unsigned int v=30;
const unsigned int r=100;
const unsigned int infinity=65535;
int ms[v][v];
void grafGenerator();
void Deixtra();
void BFS();
void Show();
void grafGenerator()
{
int i, j, m=0, n=0;
for (i=0; i<v; i++)
{
for (j=0; j<v; j++)
ms[i][j]=0;
}
for (i=0; i<r; i++)
{
n=1+(rand()%(v-1));
m=rand()%n;
if (ms[m][n]==1)
i--;
else
ms[m][n]=1;
}
for (i=0; i<v; i++)
{
for (j=0; j<=i; j++)
{ if (ms[j][i]==1)
ms[i][j]=1; } } }
void Deixtra()
{
cout << "Алгоритм Дейкстры:\n";
int s=0, g=v-1; //начальная, конечная, текущая вершины
int x[v]; //(1,0)найден, не найден кратчайший путь
int t[v]; //длина кратчайшего пути их с в и
int h[v]; //вершина, предшествующая итой вершине на кратчайшем пути
// Инициализируем начальные значения массивов
int u; // Счетчик вершин
for (u=0;u<v;u++)
{
t[u]=infinity; //Сначала все кратчайшие пути из s в i равны бесконечности
x[u]=0; } // и нет кратчайшего пути ни для одной вершины
h[s]=0; // s - начало пути, поэтому этой вершине ничего не предшествует
t[s]=0; // Кратчайший путь из s в s равен 0
x[s]=1; // Для вершины s найден кратчайший путь
int cv;
cv = s; // Делаем s текущей вершиной
while(1)
{
// Перебираем все вершины, смежные v, и ищем для них кратчайший путь
for(u=0;u<v;u++)
{
if(ms[cv][u]==0)continue; // Вершины u и cv несмежные
if(x[u]==0 && t[u]>t[cv]+ms[cv][u]) //Если для вершины u еще не
{ //найден кратчайший путь
t[u]=t[cv]+ms[cv][u]; // и новый путь в u короче чем старый, то
h[u]=cv; //запоминаем более короткую длину пути в массив t и
} } //запоминаем, что v->u часть кратчайшего пути из s->u
// Ищем из всех длин некратчайших путей самый короткий
int w=infinity; // Для поиска самого короткого пути
cv=-1; // В конце поиска v - вершина, в которую будет
// найден новый кратчайший путь. Она станет
// текущей вершиной
for(u=0;u<v;u++) // Перебираем все вершины.
{
if(x[u]==0 && t[u]<w) // Если для вершины не найден кратчайший
// путь и если длина пути в вершину u меньше
{ // уже найденной, то
cv=u; // текущей вершиной становится u-я вершина
w=t[u]; }
}
if(cv==-1)
{
cout<<"Нет пути из вершины "<<s<<" в вершину "<<g<<".\n";
break;
}
if(cv==g) // Найден кратчайший путь, выводим его
{
cout << "Кратчайший путь из вершины " << s << " в вершину " << g << ":";
u=g;
while(u!=s)
{
cout<<" "<<u;
u=h[u];
}
cout<<" "<<s<<".\nДлина пути : " << t[g] << ".\n";
break;
}
x[cv]=1;
}
}
void Show()
{
int i, j;
for (i=0; i<v; i++)
{ for (j=0; j<v; j++)
cout << ms[i][j] << " ";
cout << "\n"; }
}
void BFS()
{
cout << "Поиск в ширину:\n";
bool used[v]; //прошли вершину
int l=0;
int path[v]; //предшествующая вершина
int i, j, s=0, g=v-1; //переменные цикла, номера начальной, конечной вершин
for (i=0;i<v;i++) //инициализация
{
used[i]=false;
}
used[s]=true; //начальная вершина посещена
for (i=0; i<v;i++)
{
for (j=i; j<v; j++)
{
if (ms[i][j]!=0 && !used[j]) // найдено ребро
{
used[j]=true; //пройдена вершина
path[j]=i; } //запоминаем путь
if (used[g])
{
cout << "Кратчайший путь из вершины " << s << " в вершину " << g << " найден: "; //вывод
i=g;
while (i!=s)
{
cout << i << " ";
i=path[i];
l++;
}
cout << s;
cout << ".\nДлина: " << l << endl;
return; }
}
}
if (!used[g])
cout << "Кратчайший путь из вершины " << s << " в вершину " << g << " не найден.\n";
}
int main ()
{
setlocale (LC_ALL, "Rus");
clock_t tbfs, tdeix;
const int number=25;
double timeb[number], timed[number], totalb=0, totald=0;
srand(time(NULL));
for (int i=0; i<number; i++)
{
grafGenerator();
//Show();
tdeix=clock();
Deixtra();
timed[i]=double(clock()-tdeix)/CLOCKS_PER_SEC;
tbfs=clock();
BFS();
timeb[i]=double(clock()-tbfs)/CLOCKS_PER_SEC;
cout << "\n Время алгоритма Дейкстры: " << i << ". " << timed[i] << " секунд.\n Время алгоритма поиска в ширину:" << i << ". " << timeb[i] << " секунд.\n";
totalb+=timeb[i];
totald+=timed[i];
}
cout << "\n\n______________________________________________________________\n\n";
cout << "\n\nСреднее время алгоритма Дейкстры: " << totald/number << " секунд.";
cout << "\nСреднее время алгоритма поиска в ширину: " << totalb/number << " секунд.";
cout << "\nКоличество измерений: \t\t" << number << ".\nКоличество вершин графа: \t" << v << ".\nКоличество ребер: \t\t" << r << ".\n";
getch();
return 0;
}