Содержание отчета
Условие задачи в соответствии с вариантом.
Пошаговый подробный поиск кратчайшего остова неориентированного графа по алгоритму Дейкстра.
Выводы.
Список литературы
Пономарев В.Ф. Дискретная математика для инженеров.- Калининград: ФГОУ ВПО КГТУ, 2010.- 351 с.
Расчетно-графическая работа №8 Тема: «Поиск кратчайших путей на неориентированном графе по алгоритму Флойда».
Теоретическая часть
Пусть задан граф 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).
Итак, проверяем справедливость соотношения:
?
Ответ - Да.
Тогда:
,
;
,
Вносим изменения в матрицу
и
(рис. 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 |
1 |
|
8 |
8 |
6 |
5 |
10 |
7 |
0 |
10 |
|
18 |
15 |
13 |
15 |
9 |
12 |
10 |
0 |
2
Базовый столбец
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Рисунок 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). По матрице определяем, что кратчайший путь из в лежит через вершину (пересечение строки и столбца ). Из вершины в вершину через вершину (пересечение строки и столбца ).
Таким образом, кратчайший переход между
вершинами
и
опирается на вершины
.