Студопедия
Случайная страница | ТОМ-1 | ТОМ-2 | ТОМ-3
АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатика
ИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханика
ОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторика
СоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансы
ХимияЧерчениеЭкологияЭкономикаЭлектроника

Алгоритм Форда-Беллмана

Читайте также:
  1. Алгоритм
  2. Алгоритм RSA. Генерация ключей и функция шифрования
  3. Алгоритм STANDARD COSTING
  4. Алгоритм автоматического распараллеливания арифметических
  5. Алгоритм анализа современного урока окружающего мира
  6. Алгоритм выполнения задания
  7. Алгоритм действий при преждевременных родах.

Шаг 1. Составим матрицу длин дуг C(G)=[Cij]n

  v1 v2 v3 v4 v5 v6
v1        
v2  
v3  
v4  
v5    
v6

Строки и столбцы соответствует вершинам v1,...,v6.

По диагонали ставим . Заполняем строку v1: если существует дуга из v1 в вершину, то в соответствующем этой вершине столбце ставим число, равное длине дуги, в противном случае ставим .

  li(0) li(1) li(2) li(3) li(4) li(5)
v1 0 0 0 0 0 0
v2  
v3  
v4  
v5      
v6  

Шаг 2. Рядом с матрицей длин дуг составляем таблицу величин li(k), i = 1..6, k = 1..5.

Матрица длин дуг таблица величина дуг лi(k)

  v1 v2 v3 v4 v5 v6
v1        
v2  
v3  
v4  
v5    
v6

 

 

Заполняем первый столбец li(0) таблицы: его элементами будут 0, ∞, ∞, ∞, ∞, ∞, т.к. для v1l1(0)=0 (длина минимального пути содержащего ноль дуг из v1 в v1 ровно 0), для v2l2(0)= (длина минимального пути, содержащего ноль дуг, из v1 в v2 ровно (такого пути нет)), для v3l3(0)= ∞, для v4 l4(0)= , для v5 l5(0)= , для v6 l6(0)= .

Заполняем первую строку таблицы: ее элементами будут 0, 0, 0, 0, 0, 0, т.к. длина минимального пути, содержащего ноль дуг из v1 в v1 равна нулю l1(0)=0, длина минимального пути, содержащего одну дугу из v1 в v1 равна нулю, l1(1)=0, l1(2)=0, l1(3)=0, l1(4)=0, l1(5)=0.

Заполняем второй столбец li(1) таблицы: берем второй столбец v2 матрицы длин дуг и первый столбец таблицы li(0) и сложим их поэлементно

v2 = li(0) =   v2+li(0)=
 
 

Получили столбец v2+li(0), выберем минимальный элемент этого столбца (у нас получилась , т.к. все элементы равны ), запишем это число в строку v2 таблицы.

Далее

v3 = 5 li(0) =   v3+li(0)= 5
1

Минимальный элемент v3+li(0) равен 5, запишем это число (5) в строку v3 таблицы.

v4 = 5 li(0) =   v4+li(0)= 5
2

Минимальный элемент v4+li(0) равен 5, запишем это число (5) в строку v4 таблицы.

v5 = 2 li(0) =   v5+li(0)= 2

min = 2

v6 = 12 li(0) =   v6+li(0)= 12

min = 12

Заполняем третий столбец лi(2) таблицы: берем уже заполнений столбец лi(1) и складываем его опять со столбцами матрицы дуг v2, v3, v4, v5, v6.

li(1) = 0 v2 = li(1)+v2=
5 2
5 2
2
12

min = 7

li(1) = 0 v3 = 5 li(1)+v3= 5
5
5
2 1
12

min = 3

li(1) = 0 v4 = 5 li(1)+v4= 5
5
5
2 2
12

min = 4

li(1) = 0 v5 = 2 li(1)+v5= 2
5
5
2
12

min = 2

li(1) = 0 v6 = 12 li(1)+v6= 12
2
5
5
2
12

min = 12

Заполняем четвертый столбец li(3) таблицы: столбец li(2) складываем поочередно со столбцами матрицы дуг v2, v3, v4, v5, v6.

Пятый столбец li(4): столбец li(3) складываем поочередно со столбцами v2, v3, v4, v5, v6..

Шестой столбец li(5): столбец li(4) складываем поочередно со столбцами v2, v3, v4, v5, v6.

Шаг 3. В полученной таблице в строке v6 последнее число равно 7 - это и есть длина минимального пути из v1 в v6..

l(v1,v6) = 7.

Теперь восстановим путь. Число 7 появилась первый раз в столбце лi(4), выделим его в кружок. Число 7 появилась в результате

li(3) = 0 v6 = 12 li(1)+v6= 12
5 2 7
3
4
2
9

min = 12

В таблице число 5 обведите в кружок, 2 - в квадрат и поставьте стрелку от 5 → 7. Число 5 появилась в результате

li(2) = 0 v2 = li(3)+v2=
7
3 2 5
4 2 6
2
12

В таблице число 3 обведите в кружок, 2 - в квадрат и поставьте стрелку от 35. Число 3 появилось в результате

li(1) = 0 v3 = 5 li(3)+v3= 5
5
5
2 1 3
12

1 2 и 23

Число 2 появилось в результате

li(0) = 0 v5 = 2 li(3)+v5= 2

0 2 и 02

У нас получилось:

Число ноль стоит в строке v1, 2 в строке v5, 3-в v3, 5 - в v2, 7 - в v6.

Восстанавливаем путь: v1v5v3v2v6.

Итак, получили минимальный путь из v1 в v6 длины 7, проходящий через вершины v1, v5, v3, v2, v6.

Определение: граф со взвешенными вершинами

Иногда веса (числа vi) приписываются вершинам хi графа, и тогда получается граф со взвешенными вершинами.

Определение: граф взвешенный

Если в графе веса приписаны и дугам, и вершинам, то он называется просто взвешенным. Чаще взвешенным называют граф со взвешенными вершинами.

 

Определение: вес (длина, стоимость) пути

При рассмотрении пути м представленного последовательностью дуг (a1, a2,..., aq), за его вес (или длину, или стоимость) принимается число l(м), равное сумме весов всех дуг, входящих в м. Каждая дуга рассматривается столько раз, сколько она встречается в данном пути.

Основные определения и понятия теории графов:

петля,

контур,

цикл,


Дата добавления: 2015-07-07; просмотров: 120 | Нарушение авторских прав


<== предыдущая страница | следующая страница ==>
Граф со взвешенными дугами| Неотрицательная матрица весов

mybiblioteka.su - 2015-2024 год. (0.014 сек.)