Алгоритм Дейкстры - презентация, доклад, проект скачать

Нажмите для полного просмотра!

Содержание ▲

Вы можете ознакомиться и скачать презентацию на тему Алгоритм Дейкстры. Доклад-сообщение содержит 4 слайдов. Презентации для любого класса можно скачать бесплатно. Если материал и наш сайт презентаций Mypresentation Вам понравились – поделитесь им с друзьями с помощью социальных кнопок и добавьте в закладки в своем браузере.

Слайды и текст этой презентации

Слайд 1

Описание слайда:

Обеспечивает оптимальный маршрут прохождения пакета между отдельной парой абонентов. Обеспечивает оптимальный маршрут прохождения пакета между отдельной парой абонентов. Введем обозначения: D(v) – суммарная стоимость минимального пути от источника (узел с номером 1) до получателя (узел с номером v), l(i,j) – стоимость канала от узла i до узла j. Определена только для смежных узлов. Для несмежных равна . Это подход является алгоритмом Дейкстры для сетевой маршрутизации.

Слайд 2

Описание слайда:

Шаг0. Шаг0. Строится множество N, содержащее номер одного узла (первого). Строится таблица: строки таблицы – итерации, столбцы – номер операции, множество N, номера узлов (начиная со второго). В строке для нулевой итерации, в столбце для узла v фиксируется значение D1(v) = l(1,v). Нижний индекс показывает номер узла, через который достигается текущее оптимальное значение. Строиться корень дерева с узлом 1. Шаг k (k = 1,2,3,…). В текущей строке выбираем узел v такой, что он не из множества N, но является смежным с каким-либо из узлов множества N и такой, что значение Dp(v) минимально. Узел v включается во множество N. В дереве добавляется узел с номером v в качестве потомка узла с номером p. Далее формируется новая строка таблицы, делается пересчет. Для всех узлов wN проверяем, изменилось ли стоимость маршрута по следующему правилу: , w* – любое, , если было оставлено старое значение, иначе. Алгоритм заканчивает работу, исчерпав все множество вершин.

Слайд 3

Описание слайда:

Пример: Пример:

Слайд 4

Описание слайда:

Получено решение (маршрутная таблица) для узла с номером 1. Эта таблица расчитывается для каждого узла отдельно. Алгоритм может быть реализован самостоятельно каждым узлом. Недостатком является необходимость информации о стоимости всех каналов сети. Получено решение (маршрутная таблица) для узла с номером 1. Эта таблица расчитывается для каждого узла отдельно. Алгоритм может быть реализован самостоятельно каждым узлом. Недостатком является необходимость информации о стоимости всех каналов сети. Получатель Смежный 2 2 3 4 4 4 5 4 6 4

Теги Алгоритм Дейкстры

Похожие презентации