перейти к полному списку дипломных проектов

Ссылка на скачивания файла в формате .doc находится в конце странички

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

Идентификаторы : d[s,t] – массив длин ребер графа для каждой пары вершин s,t ?X. Если ребра нет, то соответствующий элемент этого массива содержит достаточно большое число.

х – вершина-источник графа .

n=|X| - число вершин графа.

u,w,k – рабочие переменные.

D[w] – массив, в котором к концу работы алгоритма будут содержаться кратчайшие длины путей из х в w для всех вершин w ?X.

Begin

D[x]:=0; // Длина пути из источника x.

For w ?X do D[w]:=d[x,w]; // Инициализация матрицы расстояний

For k:=1 to n-2 do // Повторять n-2 раз

For w ?{X\{x}} do // Цикл по всем вершинам, кроме источника.

For u ?X do D[w]:=min(D[w],D[u]+d[u,w]); // выбор минимума.

End.

Этот алгоритм также основан на соотношении (принципе оптимальности) Беллмана. Всякий раз, когда находится путь через транзитную вершину u, который короче найденного пути из х в w, он заменяется на более короткий путь. Это соотношение должно проверяться для любой возможной из n-2 транзитных вершин при оценке пути в каждую вершину, поэтому в алгоритме имеется цикл, определенный в строке 4.

скачать бесплатно Проектирование и разработка сетевых броузеров на основе теоретико-графовых моделей

Содержание дипломной работы

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ УКРАИНЫ
Актуальность
Цель
1.1. Основные понятия теории графов
1.2. Графовые алгоритмы
Алгоритм Форда-Беллмана
Алгоритм Дейкстры нахождения кратчайших расстояний от источника до всех остальных вершин применим только тогда
Алгоритм Форда-Фалкерсона нахождения максимального потока в сети.
Теорема Форда-Фалкерсона : максимальный поток в сети равен минимальной величине разрезов в этой сети.
Алгоритм Форда-Фалкерсона
2.1. Методы построения сетевых структур
2.2. Классификация существующих методов организации сетей
Типы кабелей
Толстый кабель обеспечивает передачу сигналов на большие расстояния
Витая пара дешевле коаксиального кабеля и менее надежна. Использование неэкранированной витой пары позволяет реализовать длину сегментов соединения до 100 метров. Для подключения витой пары используются восьмиконтактные коннекторы RG-45.
Оптоволоконный кабель имеет высокую стоимость и обладает рядом преимуществ : слабое затухание сигнала
Платы сетевого адаптера
2.3. Глобальная сеть Internet
Зарезервированные сокеты
Транслирующие серверы
Адресация Internet
Служба доменных имен (DNS)
2.4. Основы сетевой маршрутизации
Компоненты маршрутизации
Определение маршрута
Коммутация
2.5. Алгоритмы маршрутизации
Цели разработки алгоритмов маршрутизации
Оптимальность
Простота и низкие непроизводительные затраты
Живучесть и стабильность
Быстрая сходимость
Гибкость
Типы алгоритмов
Статические или динамические алгоритмы
Одномаршрутные или многомаршрутные алгоритмы
Одноуровневые или иерархические алгоритмы
Алгоритмы с интеллектом в главной вычислительной машине или в роутере
Внутридоменные или междоменные алгоритмы
Алгоритмы состояния канала или вектора расстояния
Показатели алгоритмов (метрики)
Длина маршрута
Надежность
Задержка
Полоса пропускания
Нагрузка
Стоимость связи
3.1. Описание стандартного броузера
3.2. Характеристика существующих систем поиска
3.3. Особенности создания поисковых систем в визуальных средах программирования
Приложения для работы в Internet
4.1.Архитектура системы “Броузер”
4.2.Основные процедуры броузера
4.3.Архитектура имитационной модели глобальной сети
Заключение
Список литературы :