Добавил:
Upload Опубликованный материал нарушает ваши авторские права? Сообщите нам.
Вуз: Предмет: Файл:
СиАОД_Тычинина.docx
Скачиваний:
1
Добавлен:
01.07.2025
Размер:
2 Мб
Скачать
☆
        1. Алгоритм Флойда – Уоршелла

Наиболее часто используемое название, метод получил в честь двух американских исследователей Роберта Флойда и Стивена Уоршелла, одновременно открывших его в 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");

}

Порядок выполнения работы

  1. Ознакомьтесь с теоретическим материалом и в соответствии с ним создайте новый проект.

  2. Разберите все задачи теоретической части и проверьте их работоспособность в Visual C++.

  3. Сделайте задание для самостоятельного выполнения в соответствии с номером варианта.

  4. Напишите отчет в соответствии с требованиями, приведенными на стр. 20.

  5. Потренируйтесь отвечать на контрольные вопросы.

Задание для самостоятельного выполнения

Вариант 1

Разработать программу, которая:

  • запрашивает пользователя о количестве вершин и ребер невзвешанного неориентированного графа, а также перечень существующих ребер;

  • формирует по полученной информации матрицу смежности графа;

  • осуществляет поиск в полученном графе в ширину;

  • проверить работу программы на примере графа:

Вариант 2

Разработать программу, которая:

  • запрашивает пользователя о количестве вершин и ребер взвешанного неориентированного графа, а также перечень существующих ребер и их вес;

  • формирует по полученной информации матрицу смежности графа;

  • запрашивает начальную и конечную вершину графа;

  • выводит на экран кратчайший путь между заданными вершинами и его стоимость, найденные по алгоритму Дейкстры;

  • проверить работу программы на примере графа:

Вариант 3

Разработать программу, которая:

  • запрашивает пользователя о количестве вершин и ребер взвешанного неориентированного графа, а также перечень существующих ребер и их вес;

  • формирует по полученной информации матрицу смежности графа;

  • запрашивает начальную и конечную вершину графа;

  • выводит на экран кратчайший путь между заданными вершинами и его стоимость, найденные по алгоритму Беллмана-Форда;

  • проверить работу программы на примере графа из варианта 2.

Вариант 4

Разработать программу, которая:

  • запрашивает пользователя о количестве вершин и ребер взвешанного неориентированного графа, а также перечень существующих ребер и их вес;

  • формирует по полученной информации матрицу смежности графа;

  • запрашивает начальную и конечную вершину графа;

  • выводит на экран кратчайший путь между заданными вершинами и его стоимость, найденные по алгоритму Флойда-Уоршелла;

  • проверить работу программы на примере графа из варианта 2.

Вариант 5

Разработать программу, которая:

  • запрашивает у пользователя количество вершин взвешанного ориентированного графа, матрицу смежности графа;

  • запрашивает начальную и конечную вершину графа;

  • выводит на экран кратчайший путь между заданными вершинами и его стоимость, найденные по алгоритму Дейкстры;

  • проверить работу программы на примере графа:

Вариант 6

Разработать программу, которая:

  • запрашивает пользователя о количестве вершин и ребер невзвешанного неориентированного графа, а также перечень существующих ребер;

  • формирует по полученной информации матрицу смежности графа;

  • осуществляет поиск в полученном графе в глубину;

  • проверить работу программы на примере графа из варианта 1.

Вариант 7

Разработать программу, которая:

  • запрашивает у пользователя количество вершин взвешанного ориентированного графа, матрицу смежности графа;

  • запрашивает начальную и конечную вершину графа;

  • выводит на экран кратчайший путь между заданными вершинами и его стоимость, найденные по алгоритму Беллмана-Форда;

  • проверить работу программы на примере графа из варианта 5.

Вариант 8

Разработать программу, которая:

  • запрашивает у пользователя количество вершин взвешанного ориентированного графа, матрицу смежности графа;

  • запрашивает начальную и конечную вершину графа;

  • выводит на экран кратчайший путь между заданными вершинами и его стоимость, найденные по алгоритму Флойда-Уоршелла;

  • проверить работу программы на примере графа из варианта 5.

Вариант 9

Написать программу, которая:

  • запрашивает у пользователя количество вершин невзвешанного неориентированного графа, матрицу смежности графа;

  • выводит на экран список ребер этого графа;

  • осуществляет поиск в полученном графе в ширину;

  • проверить работу программы на примере графа из варианта 1.

Вариант 10

Написать программу, которая:

  • запрашивает у пользователя количество вершин невзвешанного неориентированного графа, матрицу смежности графа;

  • выводит на экран матрицу инцедентности этого графа;

  • осуществляет поиск в полученном графе в глубину;

  • проверить работу программы на примере графа из варианта 1.

Контрольные вопросы

  1. Что такое граф?

  2. Какой граф называется орграфом?

  3. Какой граф называется взвешенным?

  4. Что такое степень вершины графа?

  5. Какие графа являются изоморфными?

  6. Назовите основные способы представления графов в памяти компьютера.

  7. Дано 2 графа. Записать их в основных формах представления графов в памяти компьютера.

  1. Назовите алгоритмы обхода графа.

  2. В каком алгоритме обхода графа используется стек?

  3. В каком алгоритме обхода графа используется очередь?

  4. Какие алгоритмы нахождения кратчайших путей на графах вы знаете?