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

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

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

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

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

	0	9		3
	9	0	2		7
		2	0	2	4	8	6
	3		2	0			5
		7	4		0	10		9
			8		10	0	7	12
			6	5		7	0	10
					9	12	10	0

а) б)

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

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

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

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

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

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

	0	9	3
	9	0
	3		0

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

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

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

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

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

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

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

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

?

Ответ - Да.

Тогда:

1. ,

;

2. ,

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

	0	9		3				Базовая строка
	9	0	2	12	7
		2	0	2	4	8	6
	3	12	2	0			5
		7	4		0	10		9
			8		10	0	7	12
			6	5		7	0	10
					9	12	10	0

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

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

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

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

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

	0	9		3
	9	0	2	12	7
		2	0	2	4
	3	12	2	0
		7	4		0

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

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

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

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

1) ? Т.е.?Да.

Тогда:

2) ? Т.е.?Да.

Тогда:

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

Тогда: .

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

Тогда:

5) ? Т.е.?Да.

Тогда:

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

	0	9	11	3	16
	9	0	2	12	7
	11	2	0	2	4	8	6
	3	12	2	0	19		5
	16	7	4	19	0	10		9
			8		10	0	7	12
			6	5		7	0	10
					9	12	10	0

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

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

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

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

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

	0	9	11	3	16
	9	0	2	12	7
	11	2	0	2	4	8	6
	3	12	2	0	19		5
	16	7	4	19	0	10
			8		10	0	7
			6	5		7	0

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

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

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

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

1) ,?Нет.

2) ,?Нет.

3) ,?Нет.

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

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

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

7) ,? Нет.

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

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

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

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

12) ,? Нет.

13) ,? Нет.

14) ,? Нет.

15) ,?Нет.

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

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

18) ,?Нет.

19) ,?Нет.

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

21) ,? Нет.

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

	0	9	11	3	15	19	17
	9	0	2	4	6	10	8
	11	2	0	2	4	8	6
	3	4	2	0	6	10	5
	15	6	4	6	0	10	10	9
	19	10	8	10	10	0	7	12
	17	8	6	5	10	7	0	10
					9	12	10	0

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

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

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

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

	0	9	11	3	16
	9	0	2	4	7
	11	2	0	2	4	8	6
	3	4	2	0	6	10	5
	16	7	4	6	0	10
			8	10	10	0	7
			6	5		7	0

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

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

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

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

3) ,? Нет.

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

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

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

7) ,? Нет.

8) ,?Нет.

9) ,?Нет.

10) ,?Нет.

11) ,?Нет.

12) ,? Нет.

13) ,? Нет.

14) ,? Нет.

15) ,?Нет.

16) ,?Нет.

17) ,?Нет.

18) ,? Нет.

19) ,? Нет.

20) ,?Нет.

21) ,? Нет.

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

	0	7	5	3	9	13	8
	7	0	2	4	6	10	8
	5	2	0	2	4	8	6
	3	4	2	0	6	10	5
	9	6	4	6	0	10	10	9 Базовая строка
	13	10	8	10	10	0	7	12
	8	8	6	5	10	7	0	10
					9	12	10	0

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

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

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

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

Поскольку ни один элемент базовой строки и базового столбца не равен , то в дальнейших расчетах используем.

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

1) ,? Нет.

2) ,?Нет.

3) ,? Нет.

4) ,?Нет.

5) ,?Нет.

6) ,?Нет.

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

8) ,?Нет.

9) ,?Нет.

10) ,?Нет.

11) ,?Нет.

12) ,?Нет.

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

14) ,? Нет.

15) ,? Нет.

16) ,? Нет.

17) ,? Нет.

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

19) ,?Нет.

20) ,?Нет.

21) ,? Нет.

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

23) ,? Нет.

24) ,?Нет.

25) ,?Нет.

26) ,? Нет.

27) ,? Нет.

28) ,? Нет.

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

	0	7	5	3	9	13	8	18
	7	0	2	4	6	10	8	15
	5	2	0	2	4	8	6	13
	3	4	2	0	6	10	5	15
	9	6	4	6	0	10	10	9 Базовая строка
	13	10	8	10	10	0	7	12
	8	8	6	5	10	7	0	10
	18	15	13	15	9	12	10	0

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

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

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

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

Поскольку ни один элемент базовой строки и базового столбца не равен , то в дальнейших расчетах используем.

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

1) ,? Нет.

2) ,?Нет.

3) ,? Нет.

4) ,?Нет.

5) ,?Нет.

6) ,?Нет.

7) ,?Нет.

8) ,?Нет.

9) ,?Нет.

10) ,?Нет.

11) ,?Нет.

12) ,?Нет.

13) ,?Нет.

14) ,? Нет.

15) ,? Нет.

16) ,? Нет.

17) ,? Нет.

18) ,? Нет.

19) ,?Нет.

20) ??Нет.

21) ,? Нет.

22) ,?Нет.

23) ,? Нет.

24) ,?Нет.

25) ,?Нет.

26) ,? Нет.

27) ,? Нет.

28) ,? Нет.

По результатам расчетов никакие изменения в матрицы ине вносятся (рис. 8.16).

	0	7	5	3	9	13	8	18
	7	0	2	4	6	10	8	15
	5	2	0	2	4	8	6	13
	3	4	2	0	6	10	5	15
	9	6	4	6	0	10	10	9
	13	10	8	10	10	0	7	12
	8	8	6	5	10	7	0	10
	18	15	13	15	9	12	10	0

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

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

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

Поскольку ни один элемент базовой строки и базового столбца не равен , то в дальнейших расчетах используем.

По результатам расчетов никакие изменения в матрицы ине вносятся.

Вычисления по алгоритму Флойда завершены.

Проверка результатов расчетов по алгоритму Флойда

С целью проверки полученных результатов выберите три варианта начальных и конечных вершин Вашего пути по графу G. Определите по графуG методом визуального анализа кратчайший путь для каждого из трех вариантов. Для каждого варианта запомните вершины, через которые проходит кратчайший путь. Повторите расчеты, но с использованием матриц кратчайших путей и кратчайших переходов. Сравните результаты. Если они совпадают, то будем считать, что расчеты матриц по алгоритму Флойда выполнены с определенной степенью достоверности правильно. Отразите результаты проверки в отчете о выполнении расчетно-графической работы. Если результаты визуального анализа графа и анализа матриц не совпадают, необходимо проверить расчеты.

Использование результатов расчетов по алгоритму Флойда

Таким образом, в результате расчетов получены матрицы кратчайших путей и кратчайших переходов графа G.

По матрицам иможно найти длину кратчайшего пути и соответствующий этому пути переход.

Пусть нас интересует длина кратчайшего пути между вершинами и. Обратимся к матрице(рисунок 8.16). На пересечении строкии столбцанаходим, что длина кратчайшего пути равна 18-ти единицам.

Для поиска соответствующего перехода будем сочетать анализ матрицы с визуальным анализом графа (рис. 8.1). По матрицеопределяем, что кратчайший путь извлежит через вершину(пересечение строкии столбца). Из вершиныв вершинучерез вершину(пересечение строкии столбца).

Таким образом, кратчайший переход между вершинами иопирается на вершины.

2. Задание

Задание на РГР формулируется следующим образом: «Найти кратчайшие пути на неориентированном графе G(рисунок 8.17) по алгоритму Флойда. Протяженность (вес) ребра приведены в таблице 8.1 , где- означает отсутствие ребра, а «1» - его наличие, которое необходимо умножить на вес ребра. Для вариантов 1-10 реброявляется дугой с направлением от вершинык, для вариантов 11-20 ребро- дугой с направлением от вершинык, для вариантов 21-30 ребро- дугой с направлением от вершинык, для вариантов 31-40 ребро- дугой с направлением от вершинык, для вариантов 41-50 ребро- дугой с направлением от вершинык».

Таблица 8.1 ― Данные для формирования графа Gпо вариантам

Старший разряд номера варианта	Индексы вершин, инцидентных ребру
	0,1	0,2	0,3	1,3	1,4	2,3	2,5	3,4	3,5	3,6
	Вес ребра (условных единиц)
	7	9	12	6	4	6	7	10	7	11
1		1		1	1	1	1	1	1	1
2	1		1	1	1	1	1	1	1
3	1		1	1	1	1	1	1	1	1
4		1	1	1	1	1	1	1	1
5	1		1	1	1	1	1	1	1	1
6		1		1	1	1	1	1	1	1
7	1		1	1	1	1	1	1	1
8			1	1	1	1	1	1	1	1
9	1		1	1	1	1	1	1	1
0		1		1	1	1	1	1	1	1

Таблица 8.1 ― Продолжение

Младший разряд номера варианта	Индексы вершин, инцидентных ребру
	4,6	4,7	5,6	5,8	6,7	6,8	6,9	7,9	8,9
	Вес ребра (условных единиц)
	2	6	4	9	8	5	4	3	9
1	1	1	1	1		1		1	1
2	1	1	1	1	1		1		1
3	1	1	1	1		1		1
4	1	1	1	1	1		1		1
5	1	1	1	1		1		1
6	1	1	1	1	1		1		1
7	1	1	1	1	1	1		1
8	1	1	1	1		1	1		1
9	1	1	1	1	1		1	1
0	1	1	1	1		1		1	1

3. Содержание отчета

1. Условие задачи в соответствии с вариантом.

2. Пошаговый подробный поиск кратчайших путей на неориентированном графе по алгоритму Флойда.

3. Проверка результатов расчетов по алгоритму Флойда.

4. Выводы.

4. Список литературы

1. Пономарев В.Ф. Дискретная математика для инженеров.- Калининград: ФГОУ ВПО КГТУ, 2010.- 351 с.