Лабораторная работа 2 Теория сложности вычислительных процессов и структур Вариант 6

Состав работы

material.view.file_icon
material.view.file_icon
material.view.file_icon matrix.py
material.view.file_icon matrix.txt
material.view.file_icon Лабораторная работа 2.docx

Необходимые программы

Работа представляет собой zip архив с файлами (распаковать онлайн), которые открываются в программах:
  • Программа для просмотра текстовых файлов
  • Microsoft Word

Описание

Теория сложности вычислительных процессов и структур
Лабораторная работа №2
Поиск кратчайшего расстояния между двумя вершинами
Присылаемый на проверку архив должен содержать 2 файла:
 файл отчета, содержащий титульный лист, условие задачи, описание используемого алгоритма, исходный текст программы (с указанием языка реализации) и результаты работы программы (можно в виде скриншотов);
 файл с исходным текстом программы (программу можно писать на любом языке программирования).

1. Задание на лабораторную работу
Написать программу, которая по алгоритму Форда-Беллмана находит кратчайшее расстояние от вершины с номером Вашего варианта (вершина 6) до всех остальных вершин связного взвешенного неориентированного графа, имеющего 10 вершин (нумерация от 0 до 9).
Граф задан матрицей смежности размера 10х10 (0 означает отсутствие ребра). Данные необходимо считывать из файла. Программа должна вывести все найденные кратчайшие расстояния и соответствующие им пути в виде последовательности ребер.

2. Теоретическая часть и описание алгоритма Форда-Беллмана
Алгоритм Форда-Беллмана — это эффективный метод динамического программирования для поиска кратчайших путей из одной фиксированной вершины-источника во все остальные вершины взвешенного графа. В отличие от алгоритма Дейкстры, данный метод корректно работает с графами, содержащими ребра с отрицательным весом.
Суть алгоритма:
Алгоритм последовательно улучшает (релаксирует) текущее знание о кратчайших расстояниях. Для графа с количеством вершин V кратчайший путь без циклов не может содержать более чем (V - 1) ребро. Поэтому алгоритм выполняет ровно (V - 1) итераций.

Пошаговое описание:
1. Инициализация: создается массив расстояний D размера V. Для стартовой вершины-источника расстояние D[start] принимается равным 0, для всех остальных вершин расстояние инициализируется бесконечностью (практически — очень большим числом). Также инициализируется массив предков P для последующего восстановления маршрутов.
2. Основной цикл (Релаксация рёбер): выполняется (V - 1) внешних итераций. На каждой итерации перебираются абсолютно все рёбра графа (u, v) с весом W. Выполняется проверка условия релаксации:
o Если D[u] + W < D[v], то мы нашли более короткий путь к вершине v через вершину u. Расстояние обновляется: D[v] = D[u] + W, а в массив предков записывается P[v] = u.
3. Восстановление путей: на основе заполненного массива предков P для каждой вершины выполняется обратный обход от целевой вершины к стартовой, формируя точную последовательность пройденных рёбер.

3. Исходные данные (Вариант 6)
Граф состоит из 10 вершин (пронумерованных от 0 до 9). Стартовая вершина-источник: 6.
Матрица смежности из задания имеет следующий вид:
Вершины 0 1 2 3 4 5 6 7 8 9
0 0 0 8 8 7 5 5 6 1 2
1 0 0 3 1 6 3 7 3 0 9
2 8 3 0 11 2 3 0 8 1 10
3 8 1 11 0 6 4 0 11 7 9
4 7 6 2 6 0 2 11 6 3 4
5 5 3 3 4 2 0 2 1 3 3
6 5 7 0 0 11 2 0 3 3 7
7 6 3 8 11 6 1 3 0 0 8
8 1 0 1 7 3 3 3 0 0 8
9 2 9 10 9 4 3 7 8 8 0
Примечание: значение 0 на пересечении строки 6 и столбцов 2 и 3 означает, что прямых рёбер из вершины 6 в вершины 2 и 3 не существует.

Дополнительная информация

Лабораторная работа 2 20.09.2026 20.09.2026 Зачет Уважаемый, замечаний нет. Галкина Марина Юрьевна
Теория сложностей вычислительных процессов и структур. Лабораторная работа №2. Вариант №6
Графы. Поиск остова минимального веса. Написать программу, которая по алгоритму Краскала находит остов минимального веса для связного взвешенного неориентированного графа, имеющего 7 вершин. Граф задан матрицей весов дуг, соединяющих всевозможные пары вершин (0 означает, что соответствующей дуги нет). Данные считать из файла. Номер варианта выбирается по последней цифре пароля.
User zhekaersh : 1 марта 2015
40 руб.
Теория сложностей вычислительных процессов и структур. Лабораторная работа №2. Вариант №6
Теория сложностей вычислительных процессов и структур. Лабораторная работа № 2 (вариант 6)
Графы. Поиск остова минимального веса. Написать программу, которая по алгоритму Краскала находит остов минимального веса для связного взвешенного неориентированного графа, имеющего 7 вершин. Граф задан матрицей весов дуг, соединяющих всевозможные пары вершин (0 означает, что соответствующей дуги нет). Данные считать из файла.
User dryan : 4 декабря 2012
40 руб.
Теория сложности вычислительных процессов и структур. Лабораторная работа №2 (2021). Вариант №6.
ЛАБОРАТОРНАЯ РАБОТА №2 Написать программу, которая по алгоритму Дейкстры (если Ваша фамилия начинается с гласной буквы) или Форда-Беллмана (если Ваша фамилия начинается с согласной буквы) находит кратчайшее расстояние от вершины с номером Вашего варианта до всех остальных вершин связного взвешенного неориентированного графа, имеющего 10 вершин (нумерация вершин начинается с 0). Граф задан матрицей смежности (0 означает, что соответствующей дуги нет). Данные считать из файла. Вывести все найден
User nik200511 : 9 июня 2021
138 руб.
Лабораторная работа № 2 по дисциплине: "Теория сложностей вычислительных процессов и структур ". 5-й семестр, 6-й вариант
Задание Написать программу, которая по алгоритму Краскала находит остов минимального веса для связного взвешенного неориентированного графа, имеющего 7 вершин. Граф задан матрицей весов дуг, соединяющих всевозможные пары вершин (0 означает, что соответствующей дуги нет). Данные считать из файла. Номер варианта выбирается по последней цифре пароля
User mastar : 18 декабря 2012
125 руб.
Гидравлика АКАДЕМИЯ ГРАЖДАНСКОЙ ЗАЩИТЫ Задача 6 Вариант 83
Определить повышение давления в трубопроводе длиной L, диаметром d и толщиной стенок δ при гидравлическом ударе, если расход воды Q, модули упругости стенок трубы Ет = 2⸱1011 Па и воды Еж = 2⸱109 Па. Время закрытия задвижки на трубопроводе tз.
User Z24 : 11 марта 2026
150 руб.
Гидравлика АКАДЕМИЯ ГРАЖДАНСКОЙ ЗАЩИТЫ Задача 6 Вариант 83
Схема подготовки нефти-Чертеж-Оборудование для добычи и подготовки нефти и газа-Курсовая работа-Дипломная работа
Схема подготовки нефти-(Формат Компас-CDW, Autocad-DWG, Adobe-PDF, Picture-Jpeg)-Чертеж-Оборудование для добычи и подготовки нефти и газа-Курсовая работа-Дипломная работа
100 руб.
Схема подготовки нефти-Чертеж-Оборудование для добычи и подготовки нефти и газа-Курсовая работа-Дипломная работа
Охорона праці вчителя
1. Загальна інформація щодо прав та зобов’язань вчителя 1.1. До роботи вчителем допускаються особи, які пройшли попередній медичний огляд, мають вищу або середню-спеціальну педагогічну освіту, при необхідності пройшли стажування протягом 2-15 змін під керівництвом досвідчених працівників, пройшли вступний та первинний (на робочому місці) інструктажі з питань охорони праці, пожежної безпеки, інструктаж і перевірку знань з електробезпеки і отримали першу кваліфікаційну групу. 1.2. В обов’язки вчи
User Qiwir : 17 апреля 2013
5 руб.
Модернізація фронтального колісного навантажувача вантажопідйомністю 3т
Вступ 1 Огляд фронтальних навантажувачів 1.1 Характеристики і призначення фронтальних навантажувачів 1.2 Вибір фронтального навантажувача 1.3 Технічний опис сучасних навантажувачів 2 Розрахунок параметрів фронтального навантажувача 2.1 Розрахунок основних параметрів навантажувача 2.2 Визначення параметрів робочого органа 2.3 Визначення реакцій на колесах навантажувача 2.4 Визначення навантажень, діючих на робоче обладнання 3 Розрахунок гідравлічної системи робочого обладнання 3.1 Визначення
User ostah : 30 августа 2014
3500 руб.
Модернізація фронтального колісного навантажувача вантажопідйомністю 3т
up Наверх