Материал: Граф и его элементы
1) кратчайший путь из вершины i в вершину m, в котором в качестве промежуточных допускается использование только первых (m - 1) вершин;
2) кратчайший путь из вершины m в вершину j, в котором в качестве промежуточных допускается использование только первых (m - 1) вершин;
) кратчайший путь из вершины i в вершину j, в котором в качестве промежуточных допускается использование только первых (m - 1) вершин.
Поскольку по предположению исходный граф не может содержать контуров
отрицательной длины, один из двух путей - путь, совпадающий с представленным в
пункте 3, или путь, являющийся объединением путей из пунктов 1 и 2 - должен
быть кратчайшим путем из вершины i в вершину j, в котором в качестве
промежуточных допускается использование только первых m вершин. Таким образом,
di,jm=min{ di,mm-1+ dm,jm-1; di,jm-1}, (3)
где di,jm - элемент матрицы Dm, di,jm-1 - элементы матрицы Dm-1 найденой на предыдущем шаге алгоритма.
Из соотношения видно, что для вычисления элементов матрицы Dm необходимо располагать лишь элементами матрицы Dm-1. Более того, соответствующие вычисления могут быть проведены без обращения к исходному графу. Теперь мм в состоянии датьформальное описание алгоритма Флойда для нахождения на графе кратчайших путей между всеми парами вершин.
Алгоритм:
) перенумеровать вершины графа от 1 до N целыми числами, определить матрицу D0, каждый элемент di,j которой есть длина кратчайшей дуги между вершинами i и j. Если такой дуги нет, положить значение элемента равным ∞. Кроме того, положить значения диагонального элемента di,iравным 0;
) для целого m, последовательно принимающего значения 1...N определить по элементам матрицы Dm-1элементы Dm;
) алгоритм заканчивается получением матрицы всех кратчайших путей
DN, N - число вершин графа. Для определения по известным элементам матрицы Dm-1
элементов матрицы Dm в алгоритме Флойда применяется рекурсивное соотношение
указанное в формуле (3).
5. Постановка задачи
Найти путь наименьшей длины между вершинами 1 и 8.
Построить коммуникационную сеть минимальной длины, используя Алгоритм
Флойда-Уоршелл.
Рисунок 11 - Граф задачи с весом ребер
6. Решение задачи аналитическим методом
Обозначим через di,jm длину кратчайшего пути из вершины i в вершину j, который в качестве промежуточных может содержать только первые m вершин графа.
На основании исходных данных формируем матрицу длин кратчайших дуг D0
(Таблица 1), каждый элемент которой равен длине кратчайшей дуги между вершинами
i и j. Если такой дуги нет, положим значение элемента равным ∞.
Таблица 1- Матрица D0
|
D0= |
|
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
|
|
1 |
0 |
1 |
5 |
9 |
9 |
∞ |
∞ |
∞ |
|
|
2 |
1 |
0 |
1 |
∞ |
∞ |
1 |
∞ |
∞ |
|
|
3 |
5 |
1 |
0 |
∞ |
∞ |
2 |
∞ |
1 |
|
|
4 |
9 |
∞ |
∞ |
0 |
9 |
∞ |
5 |
∞ |
|
|
5 |
9 |
∞ |
∞ |
9 |
0 |
∞ |
4 |
4 |
|
|
6 |
∞ |
1 |
2 |
∞ |
∞ |
0 |
∞ |
5 |
|
|
7 |
∞ |
∞ |
∞ |
5 |
4 |
∞ |
0 |
8 |
|
|
8 |
∞ |
∞ |
1 |
∞ |
4 |
5 |
8 |
0 |
Представим матрицу D1 (Таблица 2). включив в нее рассчитанные элементы из
приложения A.
Таблица 2- Матрица D1
|
D1= |
|
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
|
|
1 |
0 |
1 |
5 |
9 |
9 |
∞ |
∞ |
∞ |
|
|
2 |
1 |
0 |
1 |
10 |
10 |
1 |
∞ |
∞ |
|
|
3 |
5 |
1 |
0 |
14 |
14 |
2 |
∞ |
1 |
|
|
4 |
9 |
10 |
14 |
0 |
9 |
∞ |
5 |
∞ |
|
|
5 |
9 |
10 |
14 |
9 |
0 |
∞ |
4 |
4 |
|
|
6 |
∞ |
1 |
2 |
∞ |
∞ |
0 |
∞ |
5 |
|
|
7 |
∞ |
∞ |
∞ |
5 |
4 |
∞ |
0 |
8 |
|
|
8 |
∞ |
∞ |
1 |
∞ |
4 |
5 |
8 |
0 |
Представим матрицу D2 (Таблица 3). включив в нее рассчитанные элементы из
приложения.
Таблица 3 - Матрица D2
|
D2= |
|
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
||||||||
|
|
1 |
0 |
1 |
2 |
9 |
9 |
2 |
∞ |
∞ |
||||||||
|
|
2 |
1 |
0 |
1 |
10 |
10 |
1 |
∞ |
∞ |
||||||||
|
|
3 |
2 |
1 |
0 |
11 |
11 |
2 |
∞ |
1 |
||||||||
|
|
4 |
9 |
10 |
11 |
0 |
9 |
11 |
5 |
∞ |
||||||||
|
|
5 |
9 |
10 |
11 |
9 |
0 |
11 |
4 |
4 |
2 |
1 |
2 |
11 |
11 |
0 |
∞ |
5 |
|
|
7 |
∞ |
∞ |
∞ |
5 |
4 |
∞ |
0 |
8 |
||||||||
|
|
8 |
∞ |
∞ |
1 |
∞ |
4 |
5 |
8 |
0 |
Представим матрицу D3
(Таблица 4). включив в нее рассчитанные элементы из приложения.
Таблица 4 - Матрица D3
|
D3= |
|
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
|
|
1 |
0 |
1 |
2 |
9 |
9 |
2 |
∞ |
3 |
|
|
2 |
1 |
0 |
1 |
10 |
10 |
1 |
∞ |
2 |
|
|
3 |
2 |
1 |
0 |
11 |
11 |
2 |
∞ |
1 |
|
|
4 |
9 |
10 |
11 |
0 |
9 |
11 |
5 |
12 |
|
|
5 |
9 |
10 |
11 |
9 |
0 |
11 |
4 |
4 |
|
|
6 |
2 |
1 |
2 |
11 |
11 |
0 |
∞ |
3 |
|
|
7 |
∞ |
∞ |
∞ |
5 |
4 |
∞ |
0 |
8 |
|
|
8 |
3 |
2 |
1 |
12 |
4 |
3 |
8 |
0 |
Представим матрицу D4
(Таблица 5). включив в нее рассчитанные элементы из приложения.
Таблица 5 - Матрица D4
|
D4= |
|
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
|
|
1 |
0 |
1 |
2 |
9 |
9 |
2 |
14 |
3 |
|
|
2 |
1 |
0 |
1 |
10 |
10 |
1 |
15 |
2 |
|
|
3 |
2 |
1 |
0 |
11 |
11 |
2 |
16 |
1 |
|
|
4 |
9 |
10 |
11 |
0 |
9 |
11 |
5 |
12 |
|
|
5 |
9 |
10 |
11 |
9 |
0 |
11 |
4 |
4 |
|
|
6 |
2 |
1 |
2 |
11 |
11 |
0 |
16 |
3 |
|
|
7 |
14 |
15 |
16 |
5 |
4 |
16 |
0 |
8 |
|
|
8 |
3 |
2 |
1 |
12 |
4 |
3 |
8 |
0 |
Представим матрицу D5
(Таблица 6). включив в нее рассчитанные элементы из приложения.
Таблица 6 - Матрица D5
|
D5= |
|
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
|
|
1 |
0 |
1 |
2 |
9 |
9 |
2 |
13 |
3 |
|
|
2 |
1 |
0 |
1 |
10 |
10 |
1 |
14 |
2 |
|
|
3 |
2 |
1 |
0 |
11 |
11 |
2 |
15 |
1 |
|
|
4 |
9 |
10 |
11 |
0 |
9 |
11 |
5 |
12 |
|
|
5 |
9 |
10 |
11 |
9 |
0 |
11 |
4 |
4 |
|
|
6 |
2 |
1 |
2 |
11 |
11 |
0 |
15 |
3 |
|
|
7 |
13 |
14 |
15 |
5 |
4 |
15 |
0 |
8 |
|
|
8 |
3 |
2 |
1 |
12 |
4 |
3 |
8 |
0 |
Представим матрицу D6.
(Таблица 7). включив в нее рассчитанные элементы из приложения.
Таблица 7 - Матрица D6
|
D6= |
|
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
|
|
1 |
0 |
1 |
2 |
9 |
9 |
2 |
13 |
3 |
|
|
2 |
1 |
0 |
1 |
10 |
10 |
1 |
14 |
2 |
|
|
3 |
2 |
1 |
0 |
11 |
11 |
2 |
15 |
1 |
|
|
4 |
9 |
10 |
11 |
0 |
9 |
11 |
5 |
12 |
|
|
5 |
9 |
10 |
11 |
9 |
0 |
11 |
4 |
4 |
|
|
6 |
2 |
1 |
2 |
11 |
11 |
0 |
15 |
3 |
|
|
7 |
13 |
14 |
15 |
5 |
4 |
15 |
0 |
8 |
|
|
8 |
2 |
1 |
12 |
4 |
3 |
8 |
0 |
Представим матрицу D7.
(Таблица 8). включив в нее рассчитанные элементы из приложения.
Таблица 8 - Матрица D7
|
D7= |
|
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
|
|
1 |
0 |
1 |
2 |
9 |
9 |
2 |
13 |
3 |
|
|
2 |
1 |
0 |
1 |
10 |
10 |
1 |
14 |
2 |
|
|
3 |
2 |
1 |
0 |
11 |
11 |
2 |
15 |
1 |
|
|
4 |
9 |
10 |
11 |
0 |
9 |
11 |
5 |
12 |
|
|
5 |
9 |
10 |
11 |
9 |
0 |
11 |
4 |
4 |
|
|
6 |
2 |
1 |
2 |
11 |
11 |
0 |
15 |
3 |
|
|
7 |
13 |
14 |
15 |
5 |
4 |
15 |
0 |
8 |
|
|
8 |
3 |
2 |
1 |
12 |
4 |
3 |
8 |
0 |
Представим матрицу D8, включив в нее рассчитанные элементы.
Таблица 9 - Матрица D8
|
D8= |
|
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
|
|
1 |
0 |
1 |
2 |
9 |
7 |
2 |
11 |
3 |
|
|
2 |
1 |
0 |
1 |
10 |
6 |
1 |
10 |
2 |
|
|
3 |
2 |
1 |
0 |
11 |
5 |
2 |
9 |
1 |
|
|
4 |
9 |
10 |
11 |
0 |
9 |
11 |
5 |
12 |
|
|
5 |
7 |
6 |
5 |
9 |
0 |
7 |
4 |
4 |
|
|
6 |
2 |
1 |
2 |
11 |
7 |
0 |
11 |
3 |
|
|
7 |
11 |
10 |
9 |
5 |
4 |
11 |
0 |
8 |
|
|
8 |
3 |
2 |
1 |
12 |
4 |
3 |
8 |
0 |