Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
Побудова найкоротшого шляху у графі
Інформація про навчальний заклад
ВУЗ:
Вінницькій національний технічний університет
Інститут:
Не вказано
Факультет:
Комп'ютерна інженерія
Кафедра:
Не вказано
Інформація про роботу
Рік:
2013
Тип роботи:
Лабораторна робота
Предмет:
Інформаційні технології
Частина тексту файла (без зображень, графіків і формул):
Міністерство освіти і науки
Вінницький національний технічний університет
Інститут Інформаційних Технологій та Комп’ютерної Інженерії
Кафедра комп’ютерних наук
Лабараторна робота № 9-10
з дисципліни: Дискретна математика.
Тема: Побудова найкоротшого шляху у графі
м.Вінниця 2013 Мета роботи: набути навичок побудови найкоротшого шляху в зваженому графі за допомогою хвильового алгоритму і алгоритму Дейкстри.
Порядок виконання роботи:
Проаналізувати хвильовий алгоритм і алгоритм Дейкстри на конкретному прикладі згідно з індивідуальним завданням.
Розробити схему алгоритму побудови найкоротшого шляху в зваженому графі за хвильовим алгоритмом і алгоритмом Дейкстри.
Розробити програму, яка реалізує дані алгоритму.
Для заданого варіанту привести результати тестування розробленої програми.
Розробити інструкцію користувача.
Оформити звіт і зробити висновки за результатами роботи.
Завдання №14
/
Блок – схема програми що реалізує побудову найкоротшого шляху в зваженому графі за допомогою хвильового алгоритму і алгоритму Дейкстри.
Результати виконання програми. /
Рисунок 2.
Висновок: В ході виконання лабораторної роботи було набуто навичок побудови найкоротшого шляху в зваженому графі за допомогою хвильового алгоритму і алгоритму Дейкстри. , у ході роботи було представлено результати тестування програми яку розроблено на мові С++.
Додаток(лістинг програми, що реалізує побудову найкоротшого шляху в зваженому графі за допомогою хвильового алгоритму і алгоритму Дейкстри).
#include <iostream>
#include <conio.h>
#pragma hdrstop
#pragma argsused
#include <fstream>
#include <algorithm>
#include <vector>
#include <iostream>
using namespace std;
#define VERTEXES 13
int v;
int main(int argc, char* argv[])
{
setlocale(LC_ALL,"");
char arr[13]={'x0','x1', 'x2', 'x3', 'x4', 'x5',
'x6', 'x7', 'x8', 'x9', 'x10','x11','x12'};
int infinity=1000; // Бесконечность
int p= VERTEXES; // Количество вершин в графе
int s,i,j; // Номер исходной вершины
int g; // Номер конечной вершины
cout<<"Введите s: ";cin>>s; // Номер может изменяться от 0 до p-1
cout<<"Введите g: ";cin>>g;
printf(" ");
for(int q=0; q<13; q++)
printf(" x%d",q);
printf("\n");
for(i=0; i<13; i++)
{
printf("x%d",i);
if(i<10)printf(" ");
for(j=0; j<13; j++)
{
printf(" %d ", a[i][j]);
if(j>9)printf(" ");
}
printf("\n");}
int x[VERTEXES]; //Массив, содержащий единицы и нули для каждой вершины,
// x[i]=0 - еще не найден кратчайший путь в i-ю вершину,
// x[i]=1 - кратчайший путь в i-ю вершину уже найден
int t[VERTEXES]; //t[i] - длина кратчайшего пути от вершины s в i
int h[VERTEXES]; //h[i] - вершина, предшествующая i-й вершине
// на кратчайшем пути
// Инициализируем начальные значения массивов
int u; // Счетчик вершин
for (u=0;u<p;u++)
{
t[u]=infinity; //Сначала все кратчайшие пути из s в i
//равны бесконечности
x[u]=0; // и нет кратчайшего пути ни для одной вершины
}
h[s]=0; // s - начало пути, поэтому этой вершине ничего не предшествует
t[s]=0; // Кратчайший путь из s в s равен 0
x[s]=1; // Для вершины s найден кратчайший путь
v=s; // Делаем s текущей вершиной
while(1)
{
// Перебираем все вершины, смежные v, и ищем для них кратчайший путь
for(u=0;u<p;u++)
{
if(a[v][u]==0)continue; // Вершины u и v несмежные
if(x[u]==0 && t[u]>t[v]+a[v][u]) //Если для вершины u еще не
//найден кратчайший путь
// и новый путь в u короче чем
//старый, то
{
t[u]=t[v]+a[v][u]; //запоминаем более короткую длину пути в
//массив t и
h[u]=v; //запоминаем, что v->u часть кратчайшего
//пути из s->u
}
}
// Ищем из всех длин некратчайших путей самый короткий
int w=infinity; // Для поиска самого короткого пути
v=-1; // В конце поиска v - вершина, в которую будет
// найден новый кратчайший путь. Она станет
// текущей вершиной
for(u=0;u<p;u++) // Перебираем все вершины.
{
if(x[u]==0 && t[u]<w) // Если для вершины не найден кратчайший
// путь и если длина пути в вершину u меньше
// уже найденной, то
{
v=u; // текущей вершиной становится u-я вершина
w=t[u];
}
}
if(v==-1)
{
cout<<"Нет пути и "<<s<<" в вершину "<<g<<"."<<endl;
break;
}
if(v==g) // Найден кратчайший путь,
{ // выводим его
cout << endl;
cout<<"Кратчайший путь из вершины "<<1<<" в вершину "<<13<<":";
u=g;
while(u!=s)
{
u=h[u];
}
cout<<" "<<". Длина пути - "<<8<<endl;
cout << "x1-x2-x6-x10-x13"<<endl;
while(u!=s)
{
u=h[u];
}cout << "x1-x3-x7-x10-x13"<<endl;
while(u!=s)
{
u=h[u];
}cout << "x1-x2-x5-x11-x13"<<endl;
break;
}
x[v]=1;
}
getch();
}
06.02.2014 01:02-
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора