Расчетно-графическая работа №8

Тема: «Поиск кратчайших путей на неориентированном графе по алгоритму Флойда».

1 Теоретическая часть

Пусть задан граф G (рисунок 8.1).

Построение матрицы путей и матрицы переходов графа G

Алгоритма Флойда использует две матрицы размера , где -число вершин графа: - матрицу кратчайших путей и - матрицу кратчайших переходов. На рисунке 8.2изображены обе эти матрицы для графа G (рисунок 8.1).

 

а) б)

Рисунок 8.2 ― Матрицы кратчайших путей а) и кратчайших переходов б) графа G

Матрица переходов производна относительно матрицы путей. Для p=0 (т.е. нулевого шага работы алгоритма) элементы матрицы есть концевые вершины из перехода из в . Поэтому в каждом столбце матрицы указана вершина .

 

Шаг 0 расчетов по алгоритму Флойда

Принимаем p=0. Принимаем в матрице вершину за базовую и выделяем (штриховкой) базовую строку и базовый столбец (рис. 8.3).

 

 

Рисунок 8.3 ―Матрица путей на нулевом шаге расчетов

 

Вычеркиваем в матрице строки столбцы, базовые элементы которыхимеют значения (они на рис. 8.3 показаны более темной штриховкой), так как и всегда больше конечного значения . В итоге получаем матрицу , изображенную на рисунке 8.4.

 

 

Рисунок 8.4 - Матрица после вычеркивания строк и столбцов, базовые элементы которых имеют значение

 

Изобразим на рисунке 8.5 граф по матрице .

Обозначения: в окружность заключена базовая вершина ; каждая вершина идентифицирована дважды: переменной с индексом- цифрой и переменной с индексом-буквой

Рисунок 8.5 ― Граф

 

Выполним расчеты, для чего будем проверять справедливость соотношения:

 

Для графа на рисунке 8.5 это означает, что проверяется справедливость соотношения:

 

или иными словами: сравнивается суммарная длина пути из первой вершины до базовой , т.е. и из нулевой вершины до вершины , т.е. с длиной пути из первой вершины в третью «напрямую», т.е. (см. рис. 8.5).

 

Итак, проверяем справедливость соотношения:

?

Ответ - Да.

 

Тогда:

1) ,

;

2) ,

 

Вносим изменения в матрицу и (рис. 8.6): изменяем элемент , на ; , . Изменения выделены на рис. 8.6 красным квадратом.

								Базовая строка

	Базовый столбец

 

 

 

 

Рисунок 8.6 ― Матрицы путей и переходов графа G перед началом шага p=1

 

Шаг 1 расчетов по алгоритму Флойда

Принимаем p=1. Принимаем в матрице вершину за базовую и выделяем базовую строку и базовый столбец (рис. 8.6).

Вычеркиваем в матрице строки и столбцы, базовые элементы которых имеют значение . В итоге получаем , изображенную на рис. 8.7.

 

 

Рисунок 8.7 ― Матрица после вычеркивания строк и столбцов, базовые элементы которых имеют значение

Изобразим на рис. 8.8 граф по матрице .

 

Рисунок 8.8 ― Граф

 

Выполним необходимые расчеты:

 

1) ? Т.е. ? Да.

Тогда:

2) ? Т.е. ? Да.

Тогда:

3) ? Т.е. ? Нет.

Тогда: .

4) ? Т.е. ? Нет.

Тогда:

5) ? Т.е. ? Да.

Тогда:

 

Вносим изменения в матрицы и (рис. 8.9).

 

 

 

Рисунок 8.9 ― Матрицы путей и переходов графа G перед началом шага p=2

 

Шаг 2 расчетов по алгоритму Флойда

 

Принимаем p=2. Принимаем в матрице вершину за базовую и выделяем базовую строку и базовый столбец (рис. 8.9).

Вычеркиваем в матрице строки и столбцы, базовые элементы которых имеют значение .

В итоге получаем матрицу , изображенную на рис. 8.10.

 

Рисунок 8.10 ― Матрица после вычеркивания строк и столбцов, базовые элементы которых имеют значение

Изобразим на рисунке 8.11 граф по матрице .

Рисунок 8.11 ― Граф

 

Выполним необходимые расчеты:

 

1) , ? Нет.

2) , ? Нет.

3) , ? Нет.

4) , ? Да. Тогда: .

5) , ? Да. Тогда: .

6) , ? Да. Тогда: .

7) , ? Нет.

8) , ? Да. Тогда: .

9) , ? Да. Тогда: .

10) , ? Да. Тогда:. .