Лабораторная работа 7. Лабораторная работа 7 Тема Метод Форда Цель работы Получить практические навыки решения сетевых задач методом Форда

• Название: Лабораторная работа 7 Тема Метод Форда Цель работы Получить практические навыки решения сетевых задач методом Форда
• Дата: 14.03.2022
• Размер: 1.14 Mb.
• Имя файла: Лабораторная работа 7.pdf
• Тип: Лабораторная работа; #395256

26
Лабораторная работа № 7
Тема: «Метод Форда»
Цель работы: Получить практические навыки решения сетевых задач методом
Форда.
Предварительная подготовка: спец. дисциплина «Математические методы»
Количество часов: 2 часа
Краткая теория:
Алгоритм нахождения кратчайших путей состоит из следующих шагов:
Шаг 1. Строим матрицу смежности А, элементами которой являются веса (длины) ребер или дуг. Если пара вершин i и j не смежны, то условимся в матрице смежности А на пересечении i –ой строки и j –го столбца ставить некоторое большое число; обозначим его буквой М.
Каждому узлу j графа , кроме фиксированного, припишем вес V
j
=M, а фиксированному узлу k – все V
k
=0
Шаг 2. Берем некоторый узел
k
j 
и находим любой соседний узел i, связанный c j ребром или дугой u ij
, имеющий вес a ij
. В начальный момент в качестве узла i целесообразнее выбрать фиксированный узел k. Для j и i проверяем выполнение неравенства:
ij
i
j
a
V
V


(1)
Если оно выполняется, то прежний вес V
j узла j заменяется суммой
ij
i
j
a
V
V


. В противном случае вес V
j остается неизменным.
Операция пересчета производится для всех узлов графа до тех пор, пока ни один из узлов не сможет принимать нового значения индекса V
j
Пример.
Дан граф, содержащий семь узлов. Определите кратчайшие пути от узла k=1 от всех остальных узлов графа.
Шаг 1. Матрица смежности А, построенная для рассматриваемого графа, имеет вид( см. табл1).
В качестве фиксированного узла k примем узел 1.
Приписываем узлу 1 вес V1=0, всем остальным узлам – веса
V2=V3=V4=V5=V6=V7=M.
Рисунок 6.1.
Таблица 1
1
2
3
4
5
6
7
1
0 4
5 9
M
2
M
2
4 0
M M M
5 6
3
5
M
0 10 3
M
7
4
9
M 10 0
8
M M
5
M M
3 8
0
M
1
6
2 5
M M
M
0 3
7
M
6 7
M
1 3
0 1
6 2
3 7
4 5
1 9
2 4
5 10 3
6 7
3 8

27
Шаг 2. Просматриваем все пары узлов (i,j) и проверяем выполнение неравенства
(1). При этом процесс просмотра начнем с узлов, смежных с фиксированным. В нашем примере таким узлом является вершина 1. Величины a ij берем из матрицы смежности А
(таблица 6.1).
Для узла 2 имеем:
12 1
2
a
V
V


,
4 0 

M
,
4 2

V
Для узла 3 имеем:
13 1
3
a
V
V


,
5 0 

M
,
5 3

V
Для узла 4 имеем:
14 1
4
a
V
V


,
9 0 

M
,
9 4

V
Для узла 6 имеем:
16 1
6
a
V
V


,
2 0 

M
,
2 6

V
Проведем пересчет индексов для остальных узлов, смежных с фиксированным.
Индекс узла 5 можно найти посредством индексов узлов 4, 7 или 3. Индекс узла 7 равен
М, поэтому неравенство (1) удовлетворяться не будет.
Вычислив индекс узла 5 через узел 4, получим
45 1
4 1
5
a
V
V


,
8 9 

M
,
17 1
5

V
Приняв
17 1
5

V
за старое значение индекса, попытаемся пересчитать его через узел
3. Имеем
35 1
3 1
5
a
V
V


,
3 5
17


,
8 2
5

V
Так как условие (1) выполняется, то
17 1
5

V
заменяется на
8 2
5

V
Индекс узла 7 можно пересчитать через вершины 2, 3, 5, 6. В нашем случае, полученный через вершину 6, является минимальным
67 1
6 7
a
V
V


,
3 2 

M
,
5 1
7

V
Таким образом, индексы пересчитаны для всех узлов графа и в процессе пересчета заменены. Для того, чтобы проверить возможность дальнейшей замены индексов вершин, снова выполняем шаг 2 и пересчитываем индексы, начиная с вершин, смежных с фиксированным узлом 1. Легко проверить ,что при дальнейшем пересчете для любой пары вершин замены индексов не происходит, т.е. условие (1) уже не выполняется ни для одной пары вершин графа. Пересчет индексов вершин при этом заканчивается, а значения индексов равны:
4 2

V
2 1 
5 3

V
3 1 
9 4

V
4 1 
17 5

V
5 3
1


2 6

V
6 1 
5 1
7

V
7 6
1


Алгоритм Форда при некоторой его модификации может быть применен для
нахождения максимального пути на сетевом графике. Этот путь обычно называют
критическим.
Шаг1(предварительный). Каждой вершине j графа (j=1,2,..,N) приписывает индекс
0
)
0
(

j
V
Шаг 2 (общий). На этом шаге пере вычисляются индексы для всех вершин j графа.
Шаг 2 повторяется многократно(один, два и т.д. k раз) до тех пор, пока на очередном k-ом его повторении ни один из индексов Vj не сможет принимать новое значение
)
( k
j
V
Действие этого шага состоит в следующем. Индекс первой вершины остается без изменения:
0
)
0
(
1

V
. Все остальные вершины j (j=2,3,…,N) просматриваем в каком-нибудь порядке и заменяем индексы
)
1
( 
k
j
V
, вычисленные на предыдущем (k-1)-м повторении шага 2, на новые
)
( k
j
V
по формуле


ij
l
i
i
k
j
a
V
V


)
(
)
(
max
,
(i=1,2,..,N-1, j=2,3,..,N) где i- номера вершин, дуги из которых входят в j-ую вершину, а l равно k или (k-1) в зависимости от того, просматривалась ранее на k-ом повторении шага 2 вершина i или не просматривалась.

28
Рисунок 6.2.
Пример. Пусть дан ориентированный граф. Найти критические пути от первой вершины до всех остальных вершин графа.
Шаг1. Присвоим всем вершинам индексы
0
)
0
(

j
V
Шаг2 Определение новых значений индексов вершин. Начнем с первой просмотр всех вершин j графа.
Определим индекс вершины 2

 



4 4
0
max
12
)
0
(
1 2
0
)
1
(
2







a
V
a
V
V
i
i
Для вершины 4:

 



9 9
0
max
14
)
0
(
1 4
0
)
1
(
4







a
V
a
V
V
i
i
В вершину 3 входят две дуги, поэтому ее вес будем находить как максимум расстояний от
1-ой вершины до 3-й и от 1-ой через 4-ю до 3-й.

 



19 10 9
;
5 0
max
;
max
43
)
1
(
4 13
)
0
(
1 3
0
)
1
(
3









a
V
a
V
a
V
V
i
i
Для вершины 5:

 



22 3
19
;
8 9
max
;
max
35
)
1
(
3 45
)
0
(
4 5
0
)
1
(
5









a
V
a
V
a
V
V
i
i
Для узла 6 имеем две дуги, входящие в него: u
16
и u
36

 



9 5
4
;
2 0
max
;
max
26
)
1
(
2 16
)
0
(
1 6
)
(
)
1
(
6









a
V
a
V
a
V
V
i
l
i
Для вершины 7

 



26 1
22
;
7 19
;
6 4
;
3 9
max
;
;
;
max
57
)
1
(
5 37
)
1
(
3 27
)
1
(
2 67
)
1
(
6 7
0
)
1
(
7













a
V
a
V
a
V
a
V
a
V
V
i
i
4 2

V
2 1 
19 3

V
3 4
1


9 4

V
4 1 
22 5

V
5 3
4 1



9 6

V
6 2
1


26 1
7

V
7 3
4 1



Задания.
1.
Методом Форда, заменив дуги ребрами, найти минимальный путь на неориентированном графе.
2.
Методом Форда найти максимальный путь для ориентированного графа.
1 6
2 3
7 4
5 1
9 2
4 5
10 3
6 7
3 8

29 1
2 3
4 5
6

30 7
8 9
10 11

31 12 13 14 15 6

32 17 18 19 20 21

33 22 23 24 25
Контрольные вопросы
1.
Что такое граф? Виды графов.
2.
Способы представления графов.
3.
Что такое кратчайший путь, критический путь.
4.
Алгоритм метода Форда.