МИНОБРНАУКИ РОССИИ
Санкт-Петербургский государственный
электротехнический университет
«ЛЭТИ» им. В.И. Ульянова (Ленина)
Кафедра вычислительной техники
Отчет по лабораторной работе №4
по дисциплине «Алгоритмы и структуры данных»
Студент гр. 930 |
|
Преподаватель |
Колинько П.Г. |
Тема: Графы Вариант 35
Содержание
Введение ........................................................................................................ 3
Задание ........................................................................................................... 3
Постановка задачи и описание решения ..................................................... 3 Контрольные тесты ...................................................................................... 5
Вывод ............................................................................................................. 8
Список использованных источников........................................................... 9
Текст программы ........................................................................................... 10
Цель работы
Исследование алгоритмов для работы с ориентированными графами
Задание
Отыскание кратчайшего пути между заданной парой вершин в произвольном ориентированном графе с нагруженными ребрами
Математическая формулировка: ориентированный граф G = <V, E>, заданный в форме весового списка ребер edge [v, u], который может содержать циклы с отрицательной длиной, и вершина-источник s. Результатом является вектор расстояний d.
Постановка задачи и описание решения
Для алгоритма Форда-Беллмана более удобно представлять граф в виде списка всех рёбер (вектор структур ребра). Для такого алгоритма матрица смежности получается довольно трудно затратной.
Было решено сделать меню, в котором пользователь выбирает характеристики графа: в первом подменю он выбирает, вводить ли ему вручную или позволить компьютеру сгенерировать граф: если пользователь выбрал первый вариант, то он просто вводит данные графа с клавиатуры, иначе выводится следующее меню, в котором пользователь выбирает, какими должны быть числа в графе: положительными или положительными и отрицательными (это было сделано для того, чтобы удостовериться в правильности алгоритма Беллмана - Форда) – в таком случае генерируются однозначные числа (чтобы красиво выводилась “матрица” и наглядно показать действие алгоритма, ведь для демонстрации алгоритма можно использовать и целые числа)
Важное уточнение: если между вершинами связи нет, то вводится и выводится именно ноль
Формируется список ребер размером n*n, где n – кол-во ребер (однако обрабатываться будут только ребра с ненулевым весом, поэтому одна итерация будет повторяться [кол-во ребер] раз)
Заведём массив расстояний d[n], который после обработки будет содержать ответ на задачу: сначала мы заполняем расстояние вершины старта нулем, остальные бесконечностью. Если после действий алгоритма расстояние все равно бесконечности, значит, что эта вершина недостижима
Также в программе была учтена возможность обнаружения отрицательного цикла – такого, что алгоритм может бесконечно улучшать свою оценку, уходя в минус бесконечность.
Для восстановления пути был инициализирован p[n], в котором соответствующие вершины будут хранить предшественника. Алгоритм, предполагая, что кратчайшее расстояние до одной вершины уже посчитано, пытается улучшить кратчайшее расстояние до другой вершины. Следовательно, в момент улучшения нам надо просто запоминать в массиве “предков”, из какой вершины это улучшение произошло.
Общая сложность алгоритма – О(ne), где n – кол-во вершин, e - кол-во ребер, однако в худшем случае она может достигать O(n^3) (так как тройной цикл)
Контрольные тесты
Ввод графа с клавиатуры
Результат
верен
Генерация случайного графа с положительными весами
Генерация абсолютно случайного графа
Вывод
В данной работе были исследованы алгоритмы для работы с ориентированными графами
Реализация алгоритма заняла очень много времени, ведь он занимает так мало строк, однако совершает довольно много операций во вложенном цикле. Также трудно было реализовать восстановление пути и работу с отрицательными циклами.
Но несмотря на трудности, его интересно было реализовывать и полученные знания пригодятся в комбинаторике и работы со взвешенными графами.
Список использованных источников
Стивен Прата: Язык программирования С++. Лекции и упражнения. - 2012. – 1248 с.
Колинько П.Г.: Методические указания по дисциплине “Алгоритмы и структуры данных, часть 1”. – 2020. – 64 с.
Видеокурс по языку программирования С++ // URL: https://www.youtube.com/playlist?list=PLQOaTSbfxUtCrKs0nicOg2npJQYSPGO9r
Липский В. : Комбинаторика для программистов – 1988. – 200 с.
Сайт по алгоритмам MAXimal // URL: https://e-maxx.ru/algo/
Текст программы
#include <iostream>
#include <vector>
#include <iomanip>
#include <algorithm>
#include <conio.h>
#include <ctime>
const int inf = 1000;
int e;
using namespace std;
struct Edges {
int v, u, w;
};
class Graph
{
private:
vector <Edges> edge;
public:
Graph(int n);
//алгоритм Беллмана-Форда
void bellman_ford(int n, int s, int end);
~Graph() = default;
};
char Ch(int c) {return c + 'a';}
int enter(int n);
int length(int a);
void entero(int &option);
int main()
{
srand(time(NULL));
int i, j, weight, start, end, n;
cout << "Size of graph (<=26): "; cin >> n;
while (n>26 || n<2)
{
cout << "Wrong size!\n";
cin >> n;
}
Graph one(n);
cout << "Start vertex > ";
start = enter(n);
cout << "Final vertex > ";
end = enter(n);
one.bellman_ford(n, start - 1, end-1);
getch();
return 0;
}
Graph:: Graph(int n)
{
edge.resize(n*n);
int i, j, weight, option=-1, choice;
e = 0;
cout << "Which graph do you need?\n";
cout << "[0] manual\n";
cout << "[1] automatic\n";
cout << "Enter: ";
entero(option);
if (option)
{
cout << "What edges do you want to see in the graph?\n";
cout << "[0] Only positive ones\n";
cout << "[1] Positive and negative\n";
cout << "Enter: ";
entero(choice);
}
for (i = 0; i < n; i++)
{
for (j = 0; j < n; j++)
{
if (!option)
{
cout << Ch(i) << " -> " << Ch(j) << ": ";
cin >> weight;
}
else
{
if (!choice) weight = rand()%10;
else weight = rand()%17 -9;
//чтобы красиво выводилась таблица
}
edge[e].v = i;
edge[e].u = j;
edge[e++].w = weight;
}
cout << endl;
}
//здесь е = n*n, однако
//алгоритм не будет обрабатывать вершины с нулевым весом,
//то есть алгоритм будет работать (кол-во ребер) раз
cout << " ";
for (i = 0; i < n; i++) cout << setw(3) << (char)(i+'a');
for (i=0, j=0; i<n*n; i++)
{
if (i%n == 0)
{
cout << endl;
cout << (char)(i%n + (j++)+'a') << ':';
}
cout<<setw(3) << edge[i].w;
}
cout << endl;
}
void Graph :: bellman_ford(int n, int s, int end)
{
int i, j, x;
vector <int> d(n, inf); //расстояние до всех вершин
vector<int> p (n, -1); //массив предков соответсвующих вершин
d[s] = 0;
for (i=0;i<n-1 ;i++)
{
x = -1;
for (j = 0; j < e; j++)
if (d[edge[j].v] < inf && edge[j].w != 0) //выполняется (кол-во ребер) раз
if (d[edge[j].u] > d[edge[j].v] + edge[j].w) {
d[edge[j].u] = max(-inf, d[edge[j].v] + edge[j].w);
p[edge[j].u] = edge[j].v;
x = edge[j].u;
}
}
//Восстановление пути
if (x != -1) cout << "Negative cycle detected\n";
else if (d[end] == inf) cout << "It's impossible to reach " << Ch(end) << endl;
else
{
cout << endl << Ch(s) << "->" << Ch(end) << "=" << d[end] << endl;
cout << "No negative cycle from " << Ch(s) << endl;
vector<int> path;
for (int cur=end; cur!=-1; cur=p[cur])
path.push_back (cur);
reverse (path.begin(), path.end());
cout << "Shortest distance: ";
cout << "Path from " << Ch(s) << " to " << Ch(end) << ": ";
for (size_t i=0; i<path.size(); ++i)
cout << Ch(path[i]) << ' ';
cout << "\nShortest distances to vertices: \n";
for (i = 0; i<n; i++)
{
cout << Ch(i);
if (d[i] == inf) cout << ' ';
else
for (int j=0; j<length(d[i]); j++) cout << ' ';
}
cout << endl;
for (i = 0; i<n; i++)
if (d[i] == inf) cout << "- ";
else cout << d[i] << ' ';
cout << endl;
}
}
int enter(int n)
{
char ch;
cin >> ch;
while (ch > 'a'+ n - 1 || ch < 'a')
{
cout << "Wrong option\n";
cin >> ch;
}
return ch - 'a' + 1;
}
void entero(int &option)
{
cin >> option;
while (option < 0 || option > 1)
{
cout << "Wrong option!\n";
cin >> option;
}
}
int length(int a)
{
int c=0;
if (a != 0)
while (a!=0)
{
a /= 10;
c++;
}
else c++;
return c;
}
Санкт-Петербург
2020