Алгоритм Флойда-Уоршела

Размещено на http://www.allbest.ru/

Міністерство освіти і науки України

Національний університет «Львівська політехніка» кафедра систем автоматизованого проектування

Звіт

До розрахунково-графічної роботи

З дисципліни: «Дискретні моделі в САПР»

Виконав: студент групи КН-404

Клопенко Г.Б.

Прийняв: Каркульовський В.І.

Львів - 2021



Вступ

Варіант - 11

Індивідуальне завдання: Алгоритм Флойда-Уоршела.

Задача пошуку всіх найкоротших шляхів передбачає знаходження найкоротшого шляху між кожною парою вершин.

Звичайно вона може бути розв'язана шляхом багатократного застосування алгоритму Дейкстри з послідовним вибором кожної вершини графу в якості початкової вершини s . Проте на сьогодні розроблено більш ефективні процедури ніж багатократне повторення алгоритму Дейкстри. Одним з таких алгоритмів є алгоритм Флойда-Уоршелла.

Даний алгоритм допускає наявність дуг від'ємної довжини, але не допускає наявність контурів від'ємної довжини.

Алгоритм Флойда-Уоршелла

Дано орієнтований граф G V , E , кожній дузі (x, y) якого поставлена відповідність невід'ємна вартість c(x, y) . Задача полягає у знаходженні для кожної впорядкованої пари вершин {x, y} довільного шляху від вершини x до вершини y , довжина якого мінімальна серед всіх можливих шляхів від x до y .



Ідея алгоритму

Припустимо, що вершини графа послідовно пронумеровані від 1 до n . Алгоритм використовує матрицю A розміру n n , в якій обчислюються довжини найкоротших шляхів. На початку елемент (i, j) дорівнює відстані dij від вузла i до вузла j , якщо існує дуга (i, j) і дорівнює нескінченності в іншому випадку. Кожен діагональний елемент матриці A дорівняю нулю. Над матрицею A виконується n ітерацій. Після k -ї ітерації елемент A i, j містить значення найкоротшого шляху з вершини i в вершину j , що не проходить через вершини з номером більшим k . Іншими словами, між кінцевими вершинами i та j можуть знаходитися лише вершини, номера яких менші або дорівнюють k.

На k -й ітерації для обчислення матриці A використовується формула:

Ak [i, j] min Ak 1[i, j], Ak 1 [i, k] Ak 1[k, j] ,

де індекс k - означає значення матриці після k -ї ітерації.

Формула (2.1) інтерпретується наступним чином. Нехай є три вузли i ,

і k к та задані відстані між ними (рис. 2.2).

Рис.2.2. Трикутний оператор Флойда (тобто вартість шляху від вершини i до вершини j без участі вершини k )

величиною Ak 1[i, k] Ak 1[k, j] (тобто вартість шляху від вершини i до вершини k плюс вартість шляху від вершини k до вершини j ). Якщо

шлях через проміжну вершину k дешевше, ніж Ak 1[i, j] , то величина Ak [i, j] змінюється.

Така заміна (далі її умовно називатимемо трикутним оператором)

Виконується систематично в процесі виконання алгоритму Флойда-

Уоршелла.

Формалізація алгоритму Флойда-Уоршелла

Етап 0. Визначаємо початкову матрицю відстаней D0 і матрицю послідовності вузлів S0 . Діагональні елементи обох матриць позначаються знаком "-", що показує, що ці елементи в обчисленнях участь не беруть. Вважаємо k 1.

		1	2	…	j	…	n
	1	--	d12	…	d1j	…	d1n
D0	2	d21	--	…	d2j	…	d2n
	…	…	…	…	…	…	…
	i	di1	di2	…	dij	…	din
	…	...	…	…	...	…	...
	N	dn1	dn2	…	dnj	…	--
		1	2	…	j	…	n
	1		2	...	j	...	п
	2	1	--	...	j	...	п
S0	…	...	...	...	...	...	...
	i	1	2	...	j	...	п
	…	...	...	...	...	...	...
	N	1	2		j	...	--

Основний етап к. Задаємо рядок k і стовпець k як провідний рядок і провідний стовпець. Розглядаємо можливість використання трикутного оператора до всіх елементів dij матриці. Якщо виконується нерівність

dik d kj dij



то робимо наступне:

створюємо матрицю Dk шляхом заміни в матриці Dk 1 елемента dij сумою dik dkj ;

створюємо матрицю S k , змінюючи в матриці Sk 1 елемент sij на k .

Вважаємо k k 1 і повторюємо етап k.

.

Рис.1. Блок-схема алгоритму

Після реалізації n етапів алгоритму визначення по матрицях Dn і S n найкоротшої відстані між вузлами i та j виконується по наступних правилах.

Відстань між вузлами і та j дорівнює елементу dij в матриці Dn .

Проміжні вузли шляху від вузла i до вузла j визначаються по матриці S n . Хай sij k , тоді маємо шлях i k j . Якщо далі sik k і skj j , тоді вважаємо, що весь шлях визначений, оскільки знайдені всі проміжні вузли. Інакше повторюємо описану процедуру для шляхів від вузла i до вузла k і від вузла k до вузла j. вершина граф дуга алгоритм

Програмна реалізація

#include "DistanceMatrix.h"

#include<typeinfo>

#include<iostream>

#include<algorithm>

#include<string>

using DistVec = std::vector<Distance>;

std::istream& operator>>(std::istream& is, DistanceMatrix& d)

{

int u, v, w, V, E;

is >> V >> E;

d.mV = V - 1;

d.mE = E;

//is >> u >> v >> w;

d.mDistMatrix.resize(d.mV, std::vector<Distance>(d.mV));

d.mNext.resize(d.mV, std::vector<int>(d.mV));

//for (auto& inner : d.mDistMatrix)

// for (auto& i : inner)

// {

// is >> u >> v >> w;

// i.setWeight(w);

// }

for (int i = 0; i<d.mE; ++i)

{

is >> u >> v >> w;

d.mDistMatrix[u - 1][v - 1].setWeight(w);

d.mNext[u - 1][v - 1] = u - 1;

}

for (int i = 0; i <d.mV; ++i)

{

d.mDistMatrix[i][i].setWeight(0);

d.mNext[i][i] = i;

}

//std::cout << "-------" << __FUNCTION__ <<"---------" << std::endl;

//d.showmNext();

//std::cout << "----------------" << std::endl;

return is;

}

std::ostream & operator<<(std::ostream & os, DistanceMatrix & d)

{

os << typeid(d).name() << d.mV << d.mE;

std::cout << std::endl;

for (const auto& inner : d.mDistMatrix) {

for (const auto& item : inner) {

std::cout.width(5);

os << item << " ";

}

std::cout << std::endl;

}

return os;

}

std::string DistanceMatrix::getPath(int i, int j)

{

if (mDistMatrix[i][j].isInfinite())

return "inf";

int intermediate = mNext[i][j];

std::string path{};

if (intermediate == i)

return "-";

//if (mNext[i][j] == i)

// return "-";

else

path = getPath(i, intermediate) + std::to_string(intermediate + 1) + getPath(intermediate, j);

return path;

}

bool DistanceMatrix::floyd_warshall()

{

for (int k = 0; k < mV; ++k)

for (int i = 0; i < mV; ++i)

for (int j = 0; j < mV; ++j)

{

if (mDistMatrix[i][j] > mDistMatrix[i][k] + mDistMatrix[k][j])

{

std::cout << "k: " << k << "\ti: " << i << "\tk: " << j << std::endl;

mDistMatrix[i][j] = mDistMatrix[i][k] + mDistMatrix[k][j];

//printMatrix();

//mNext[i][j] = mNext[k][j];

mNext[i][j] = k;

//std::cout << "-------" << "mNext table"<< "---------" << std::endl;

//showmNext();

}

}

//std::cout << "-------" << __FUNCTION__ << "---------" << std::endl;

//showmNext();

//std::cout << "----------------" << std::endl;

std::cout << "------------RESULT-------------" << std::endl;

for (int i = 0; i < mV; ++i)

{

std::cout << std::endl;

for (int j = 0; j < mV; ++j)

{

if (i != j)

{

std::cout << "d[" << i + 1 << ", " << j + 1 << "]\t";

std::cout << "\tPATH: " << i + 1 << getPath(i, j) << j + 1 << std::endl;

}

}

}

return true;

}

void DistanceMatrix::printMatrix() const

{

std::for_each(mDistMatrix.cbegin(), mDistMatrix.cend(), [](auto& dv) {

std::for_each(dv.cbegin(), dv.cend(), [](auto &d) {

std::cout.width(5);

std::cout << d << " ";

});

std::cout << std::endl;

} );

std::cout << std::endl;

}

void DistanceMatrix::showmNext() const

{

std::for_each(mNext.cbegin(), mNext.cend(), [](auto& p) {

std::for_each(p.cbegin(), p.cend(), [](auto &d) {

std::cout.width(5);

std::cout << d << " ";

});

std::cout << std::endl;

});

std::cout << std::endl;

}

Рис.3. Результат виконання програми



Висновки

Під час виконання розрахунково-графічної роботи було реалізовано код програми відповідно до індивідуального завдання, наведена блок-схема та скріншот виконання програми. Алгоритм Флойда-Уоршела використовуєтся для знаходження мінімального шляху між двома будь якими вершинами у графі. Його головною особливістю є те, що в ньому допускається наявність дуг з від'ємною вагою.

Размещено на Allbest.ru