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

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

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

Шаг 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 - в квадрат и поставьте стрелку от 3 5. Число 3 появилось в результате

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

1 2 и 2 3

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

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

0 2 и 0 2

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

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

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

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

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

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

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

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

 

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

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

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

петля,

контур,

цикл,

Доверь свою работу ✍️ кандидату наук!
1500+ квалифицированных специалистов готовы вам помочь

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


 

 

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

mybiblioteka.su - 2015-2022 год. (0.036 сек.)