- •Введение
- •Анализ сложности алгоритма [2, 8]
- •Требования к оформлению отчетов по лабораторным работам
- •Лабораторная работа №1
- •Разработка линейных программ.
- •Теоретическая часть
- •Библиотека математических функций
- •Теоретическая часть
- •Варианты задания
- •Лабораторная работа №2. Базовые структуры алгоритмов.
- •Варианты задания
- •Варианты задания
- •Лабораторная работа №3 Одномерные массивы и указатели
- •Теоретическая часть [3]
- •Контрольные вопросы
- •Лабораторная работа №4 Двумерные массивы
- •Теоретическая часть [1, 3]
- •Лабораторная работа №5 Строки и файлы. Файловые операции ввода-вывода
- •Теоретическая часть [1, 3].
- •Значения режимов открытия.
- •Задания для самостоятельного выполнения
- •Лабораторная работа №6 Функции
- •Теоретическая часть [1, 3]
- •Лабораторная работа №7 Сортировка массивов
- •Теоретическая часть [2, 4, 5]
- •Варианты задания
- •Лабораторная работа № 8 Структуры данных
- •Теоретическая часть [1, 3]
- •I. Исходные данные, результаты и промежуточные величины
- •II. Алгоритм решения задачи очевиден:
- •III. Программа и тестовые примеры
- •Контрольные вопросы
- •Лабораторная работа №9 Поиск в массивах
- •Теоретическая часть [2, 5, 6]
- •Разрешение коллизий
- •Лабораторная работа №10 Поиск подстроки
- •Теоретическая часть [2, 6]
- •Лабораторная работа №11 Динамические структуры данных
- •Теоретическая часть [1, 3]
- •Лабораторная работа №12 Алгоритмы на графах
- •Теоретическая часть [7]
- •Основные понятия и виды графов
- •Способы представления графов
- •Матрица инцидентности
- •Список смежности
- •Список ребер
- •Алгоритм Дейкстры
- •Алгоритм Беллмана — Форда
- •Алгоритм Флойда – Уоршелла
- •Заключение
- •Библиографический список
- •Оглавление
Алгоритм Флойда – Уоршелла
Наиболее часто используемое название, метод получил в честь двух американских исследователей Роберта Флойда и Стивена Уоршелла, одновременно открывших его в 1962 году. Но иногда встречаются и другие варианты наименований: алгоритм Рой – Уоршелла или алгоритм Рой – Флойда. Рой – фамилия профессора, который разработал аналогичный алгоритм на 3 года раньше (в 1959 г.) коллег, но это его открытие осталось безвестным. Алгоритм Флойда – Уоршелла – динамический алгоритм вычисления значений кратчайших путей для каждой из вершин графа. Метод работает на взвешенных графах, с положительными и отрицательными весами ребер, но без отрицательных циклов, являясь, таким образом, более общим в сравнении с алгоритмом Дейкстры, т. к. последний не работает с отрицательными весами ребер, и к тому же классическая его реализация подразумевает определение оптимальных расстояний от одной вершины до всех остальных.
Для реализации алгоритма Флойда – Уоршелла сформируем матрицу смежностиD[][] графа G=(V, E), в котором каждая вершина пронумерована от 1 до |V|. Эта матрица имеет размер |V|×|V|, и каждому ее элементу D[i][j] присвоен вес ребра, идущего из вершины i в вершину j. По мере выполнения алгоритма, данная матрица будет перезаписываться: в каждую из ее ячеек внесется значение, определяющее оптимальную длину пути из вершины i в вершину j (отказ от выделения специального массива для этой цели сохранит память и время). Теперь, перед составлением основной части алгоритма, необходимо разобраться с содержанием матрицы кратчайших путей. Поскольку каждый ее элемент D[i][j] должен содержать наименьший из имеющихся маршрутов, сразу можно сказать, что для единичной вершины он равен нулю, даже если она имеет петлю (отрицательные циклы не рассматриваются), следовательно, все элементы главной диагонали (D[i][i]) нужно обнулить.
Ключевая часть алгоритма, состоя из трех циклов, выражения и двух условных операторов, записывается довольно компактно:
Для k от 1 до |V| выполнять;
Для i от 1 до |V| выполнять;
Для j от 1 до |V| выполнять;
Если веса i->k и k->j не нулевые, и i не равно j, то;
Если вес i->k + вес k->j меньше веса i->j, то заменить его их суммой.
Кратчайший путь из вершины i в вершину j может проходить, как только через них самих, так и через множество других вершин k∈(1, …, |V|). Оптимальным из i в j будет путь или не проходящий через k, или проходящий. Заключить о наличии второго случая, значит установить, что такой путь идет из i до k, а затем из k до j, поэтому должно заменить, значение кратчайшего пути D[i][j] суммой D[i][k]+D[k][j].
Реализация алгоритма Флойда – Уоршелла на C++:
#include <iostream>
using namespace std;
const int maxV=1000;
int i, j, n;
int GR[maxV][maxV];
//алгоритм Флойда-Уоршелла
void FU(int D[][maxV], int V){
int k;
for (i=0; i<V; i++) D[i][i]=0;
for (k=0; k<V; k++)
for (i=0; i<V; i++)
for (j=0; j<V; j++)
if (D[i][k] && D[k][j] && i!=j)
if (D[i][k]+D[k][j]<D[i][j] || D[i][j]==0)
D[i][j]=D[i][k]+D[k][j];
for (i=0; i<V; i++) {
for (j=0; j<V; j++) cout<<D[i][j]<<"\t";
cout<<endl;
}
}
//главная функция
void main(){
setlocale(LC_ALL, "Rus");
cout<<"Количество вершин в графе > "; cin>>n;
cout<<"Введите матрицу весов ребер:\n";
for (i=0; i<n; i++)
for (j=0; j<n; j++){
cout<<"GR["<<i+1<<"]["<<j+1<<"] > ";
cin>>GR[i][j];
}
cout<<"Матрица кратчайших путей:"<<endl;
FU(GR, n);
system("pause");
}
Порядок выполнения работы
Ознакомьтесь с теоретическим материалом и в соответствии с ним создайте новый проект.
Разберите все задачи теоретической части и проверьте их работоспособность в Visual C++.
Сделайте задание для самостоятельного выполнения в соответствии с номером варианта.
Напишите отчет в соответствии с требованиями, приведенными на стр. 20.
Потренируйтесь отвечать на контрольные вопросы.
Задание для самостоятельного выполнения
Вариант 1
Разработать программу, которая:
запрашивает пользователя о количестве вершин и ребер невзвешанного неориентированного графа, а также перечень существующих ребер;
формирует по полученной информации матрицу смежности графа;
осуществляет поиск в полученном графе в ширину;
проверить работу программы на примере графа:
Вариант 2
Разработать программу, которая:
запрашивает пользователя о количестве вершин и ребер взвешанного неориентированного графа, а также перечень существующих ребер и их вес;
формирует по полученной информации матрицу смежности графа;
запрашивает начальную и конечную вершину графа;
выводит на экран кратчайший путь между заданными вершинами и его стоимость, найденные по алгоритму Дейкстры;
проверить работу программы на примере графа:
Вариант 3
Разработать программу, которая:
запрашивает пользователя о количестве вершин и ребер взвешанного неориентированного графа, а также перечень существующих ребер и их вес;
формирует по полученной информации матрицу смежности графа;
запрашивает начальную и конечную вершину графа;
выводит на экран кратчайший путь между заданными вершинами и его стоимость, найденные по алгоритму Беллмана-Форда;
проверить работу программы на примере графа из варианта 2.
Вариант 4
Разработать программу, которая:
запрашивает пользователя о количестве вершин и ребер взвешанного неориентированного графа, а также перечень существующих ребер и их вес;
формирует по полученной информации матрицу смежности графа;
запрашивает начальную и конечную вершину графа;
выводит на экран кратчайший путь между заданными вершинами и его стоимость, найденные по алгоритму Флойда-Уоршелла;
проверить работу программы на примере графа из варианта 2.
Вариант 5
Разработать программу, которая:
запрашивает у пользователя количество вершин взвешанного ориентированного графа, матрицу смежности графа;
запрашивает начальную и конечную вершину графа;
выводит на экран кратчайший путь между заданными вершинами и его стоимость, найденные по алгоритму Дейкстры;
проверить работу программы на примере графа:
Вариант 6
Разработать программу, которая:
запрашивает пользователя о количестве вершин и ребер невзвешанного неориентированного графа, а также перечень существующих ребер;
формирует по полученной информации матрицу смежности графа;
осуществляет поиск в полученном графе в глубину;
проверить работу программы на примере графа из варианта 1.
Вариант 7
Разработать программу, которая:
запрашивает у пользователя количество вершин взвешанного ориентированного графа, матрицу смежности графа;
запрашивает начальную и конечную вершину графа;
выводит на экран кратчайший путь между заданными вершинами и его стоимость, найденные по алгоритму Беллмана-Форда;
проверить работу программы на примере графа из варианта 5.
Вариант 8
Разработать программу, которая:
запрашивает у пользователя количество вершин взвешанного ориентированного графа, матрицу смежности графа;
запрашивает начальную и конечную вершину графа;
выводит на экран кратчайший путь между заданными вершинами и его стоимость, найденные по алгоритму Флойда-Уоршелла;
проверить работу программы на примере графа из варианта 5.
Вариант 9
Написать программу, которая:
запрашивает у пользователя количество вершин невзвешанного неориентированного графа, матрицу смежности графа;
выводит на экран список ребер этого графа;
осуществляет поиск в полученном графе в ширину;
проверить работу программы на примере графа из варианта 1.
Вариант 10
Написать программу, которая:
запрашивает у пользователя количество вершин невзвешанного неориентированного графа, матрицу смежности графа;
выводит на экран матрицу инцедентности этого графа;
осуществляет поиск в полученном графе в глубину;
проверить работу программы на примере графа из варианта 1.
Контрольные вопросы
Что такое граф?
Какой граф называется орграфом?
Какой граф называется взвешенным?
Что такое степень вершины графа?
Какие графа являются изоморфными?
Назовите основные способы представления графов в памяти компьютера.
Дано 2 графа. Записать их в основных формах представления графов в памяти компьютера.
Назовите алгоритмы обхода графа.
В каком алгоритме обхода графа используется стек?
В каком алгоритме обхода графа используется очередь?
Какие алгоритмы нахождения кратчайших путей на графах вы знаете?
