Отчет Пр9

ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ БЮДЖЕТНОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ ВЫСШЕГО ОБРАЗОВАНИЯ

«САНКТ-ПЕТЕРБУРГСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ ТЕЛЕКОММУНИКАЦИЙ ИМ. ПРОФ. М.А. БОНЧ-БРУЕВИЧА»

(СПбГУТ)

Кафедра безопасности информационных систем

ОТЧЁТ

по практической работе № 9 на тему: «Нахождение кратчайшего маршрута»

по дисциплине «Алгоритмы и структуры данных»

Выполнил: студент группы ИСТ-114, Медведева С.Г.,

«30» ноября 2022 г. ___________/Медведева С.Г.

Принял: к.ф.-м.н., доцент, И.А. Моисеев

«30» ноября 2022 г. ___________/ И.А. Моисеев /

1 Основная часть

1. Цель работы

Используя алгоритм Дейкстры, составит программу, находящую требуемый маршрут.

2. Результаты выполнения работы

1. #include <iostream> #include <fstream> using namespace std; void Read_Mat(int m, int **array, ifstream &file) { if (file.is_open()) { auto i = 0, j = 0; while (!file.eof()) { file >> array[i][j]; j < m - 1 ? j++ : j = 0; if (j == 0) i++; } } else cout << "File is not open"; } void PrintArray(int **arr, int n, int m) { for (int i{}; i < n; i++) { for (int j{}; j < m; j++) { cout << arr[i][j] << " "; } cout << endl; } } int isArray(bool* arr, int size) { int count{}; for (int i = 0; i < size; ++i) { count += arr[i]; } return count; } void f(int** arr, int size, bool* visited, int* history, int weight = 0, int v = 0,int min = INT32_MAX) { history[isArray(visited, size)] = v; visited[v] = true; if (isArray(visited, size) == size) { if (min > weight + arr[v][0]) { min = weight + arr[v][0]; if (weight + arr[v][0] == min) { for (int i = 0; i < size; ++i) { cout << history[i] + 1 << " -> "; } cout << 1 << " sum = " << min << endl; } } } else { for (int i = 0; i < size; ++i) { if (i != v && !visited[i]) { f(arr, size, visited, history, weight + arr[v][i], i, min); } } } visited[v] = false; } int foo(int** arr, int size) { bool* visit = new bool[size]; int* history = new int[size]; for (int i{}; i < size; i++) { visit[i] = false; history[i] = 0; } f(arr, size, visit, history, 0, 0); } int main() { ifstream fin(R"(C:\Users\sonik\CLionProjects\Lab9\file.txt)"); int n = 5, m = 5; int **array_a = new int *[m]; for (int i = 0; i < m; i++) { array_a[i] = new int[n]; } bool *arrayB = new bool[m]; int firstV{1}, endV{}; Read_Mat(m, array_a, fin); //cout << endl << "Матрица смежности:" << endl; //PrintArray(array_a, n, m); for (int i{}; i < m; i++) { arrayB[i] = false; } //arrayB[0] = true; //int minSumma{0}; foo(array_a, n); return 0; }

САНКТ-ПЕТЕРБУГР

2022