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