Нахождение максимальной пропускной способности в сети

Август 3, 2022

Главная
Информатика
Нахождение максимальной пропускной способности в сети

Содержание

2. Алгоритм Белла Форда Псевдокод BellmanFord(G, w, s) d[s] ← 0 for each v ∈ V −
3. +возможность работы с отрицательными циклами и их поиск +быстрее алгоритма Дейкстры и Флойда-Уоршелла - реализация сложнее
4. Средства реализации Интерфейс визуализации: Microsoft GLEE для Visual Studio Язык программирования: C#
5. Шаг 1
6. Шаг 2
7. Шаг 3
8. Шаг 4
9. Заключение Алгоритм Беллмана-Форда используется в протоколах маршрутизации семейства “distance-vector routing”, например, в протоколе RIP версий 1
11. Скачать презентацию

Слайд 2

Алгоритм Белла Форда
Псевдокод
BellmanFord(G, w, s)
d[s] ← 0
for each v

∈ V − {s}
do d[v] ← ∞
for i ← 1 to |V | − 1
do for each (u, v) ∈ E
do if d[v] > d[u] + w(u, v) //релаксация дуги
then d[v] ← d[u] + w(u, v)
for each (u, v) ∈ E //проверка наличия отрицательных циклов
do if d[v] > d[u] + w(u, v) //релаксация возможна?
then return False //есть отрицательный цикл
return d
Сложность выполнения О(n*m)

Слайд 3

+возможность работы с отрицательными циклами и их поиск +быстрее алгоритма Дейкстры и

Флойда-Уоршелла - реализация сложнее алгоритма Флойда-Уоршелла

Достоинства и недостатки алгоритма

Слайд 4

Средства реализации
Интерфейс визуализации: Microsoft GLEE для Visual Studio
Язык программирования: C#

Слайд 5

Шаг 1

Слайд 6

Шаг 2

Слайд 7

Шаг 3

Слайд 8

Шаг 4

Слайд 9

Заключение
Алгоритм Беллмана-Форда используется в протоколах маршрутизации семейства
“distance-vector routing”, например,

в протоколе
RIP версий 1 и 2.
Может использоваться в навигационных системах