Sbornik_ispr

m

Рис. 2.10. Структура графа, приведенного Рис. 2.11. Структура графа, на рис. 2.9 при lm =1. приведенного на рис. 2.9

при lm =0.

Метод последовательного разложения позволяет свести расчет структурной надежности непараллельно-последовательного графа к расчету структурной надежности параллельно-последовательных графов.

Значения коэффициентов готовности каналов тональной частоты (ТЧ) и

основных цифровых каналов (ОЦ) на телефонных сетях Российской Федерации приведены в таблице 2.2.

21

4. Варианты заданий

Варианты заданий представлены на рис.1.4 и 1.5 и в таблицах 1.1 и 1.2 по теме 1: «Структурные матрицы сетей и операции с ними».

5.Содержание отчета

1.Вариант задания графа сети и исходные данные.

ВУЗов. – М.: Дрофа, 2008. – 239 с.

2. Нетес В.А. Основы теории надёжности: Учебное пособие/МТУСИ. –

М.,2006.

Тема 3

Алгоритм Дейкстры поиска кратчайшего пути

1. Цель работы

Изучить и практически освоить алгоритм Дейкстры поиска кратчайшего

пути.

2.Задание

1.Изучить алгоритм Дейкстры.

2.Используя алгоритм Дейкстры, найти кратчайший путь из вершины s к

вершине t.

22

Исходные данные для расчета по двадцати вариантам представлены в таблице 3.2. Вариант задаётся преподавателем: может выбираться, например,

по последней цифре номера зачетной книжки или по номеру в групповом журнале.

3. Теоретическая часть

Задача поиска кратчайшего пути наиболее часто встречается на практике.

Под кратчайшим путем может пониматься путь минимальной длины,

минимальной стоимости или по любым другим весовым коэффициентам,

присваиваемым ветвям (ребрам) графа.

Пусть задан ориентированный граф (рис. 3.1.).

Рис. 3.1. Ориентированный граф

Пусть длина каждого ребра выражается неотрицательным числом c i j ≥ 0 .

Алгоритм поиска кратчайшего пути из s в t включает следующие три

шага.

Шаг 1. Постоянный вес вершины s = 0 и временные веса δj = ∞, для всех j s. Положим i=s, где i-номер последней вершины с постоянным весом.

23

Шаг 2. Для каждой вершины с временным весом пересчитываем

переходим к шагу 2.

Алгоритм Дейкстры позволяет построить дерево кратчайших путей из вершины s во все вершины исходного графа. Для этого шаг 3 нужно изменить следующим образом: если всем вершинам приписаны постоянные веса, то дерево кратчайших путей с корнем в вершине s найдено. В противном случае перейти к шагу 2.

Пример реализации алгоритма для графа, приведенного на рис. 3.1.

Принимаем i=s; i равно номеру вершины с последним постоянным

весом.

Шаг 2. Рассчитаем веса остальных вершин:

1 = min 1 ; s + cs1 = min ∞, 0+4 = 4.2 = min 2 ; s + cs2 = min ∞, 0+∞ = ∞.3 = min 3 ; s + cs3 = min ∞, 0+3 = 3.

4 = ∞.t = ∞.

24

Минимальный вес имеет вершина 3, ей приписываем постоянный вес

3 =3.

Положим i=3.

Шаг 3. Так как i = 3 t, то переходим к шагу 2.

Текущее дерево имеет следующий вид:

Вторая итерация

Шаг 2. Так как найдено новое значение i =3 t, то пересчитываем временные веса остальных вершин.

1 = min 1 ; 3 + c31 = min 4, 3+∞ = 4.2 = min 2 ; 3 + c32 = min ∞, 3+∞ = ∞.4 = min 4 ; 3 + c34 = min ∞, 3+3 = 6.

t = ∞.

Минимальный вес имеет вершина 1. Приписываем ей постоянный вес

1 = 4. Положим i =1.

Шаг 3. Так как i = 1 t, переходим к шагу 2.Текущее дерево путей

имеет следующий вид:

1

4

S

3

3

25

Третья итерация

Шаг 2. Так как найдено новое значение i=1 t, то пересчитываем

временные веса вершин.

2 min 2 ; 1 + c12 min ;4 min 4 ; 1 + c14 = min ;t min t ; 1 + c1t .

Минимальный вес имеет вершина 4. Приписываем ей постоянный вес

4 = 6.

Положим i = 4.

Шаг3. Так как i = 4 ≠ t, переходим к шагу 2.

Текущее дерево путей имеет следующий вид:

1

4

s

3

Или

1

4

2

s

3

Так как из вершины s в вершину i = 4 имеется два пути с одинаковым весом, то из двух путей можно выбрать любой (в дальнейших расчетах выбран первый).

26

Четвертая итерация

Шаг 2. Так как найдено новое значение i =4 t, то пересчитываем

временные веса вершин.

2 min 2 ; 4 + c42 min ;

t min 2 ; 4 + c4t min .

Минимальный вес имеет вершина 2. Присваиваем ей постоянный вес

2 = 7. Положим i = 2.

Шаг 3. Так как i = 2 t, переходим к шагу 2.

Текущее дерево путей имеет следующий вид:

4 1 3 2

S

27

Таким образом, из вершины s в вершину t найден кратчайший путь с весом, t =8 равным 8 .

При расчетах веса узлов и вид текущего дерева на каждой итерации заносятся в таблицу 3.1.

Литература

1.Филлипс Д., Гарсиа-Диас А. Методы анализа сетей. – М.: Мир, 1984.

2.Теория сетей связи / Под ред. В.Н. Рогинского. – М., Связь, 1981.

3.Форд Л.Р., Фалкерсон. Потоки в сетях. – М. Мир, 1966.

4.Майника Э. Алгоритмы оптимизации на сетях и графах: Пер. с англ. – М.:

Мир, 1981.

4. Варианты заданий

Исходные данные для расчета по двадцати вариантам представлены в

таблице 3.2.

5.Содержание отчёта

1.Описание процедуры расчета по итерациям и шагам (при ручном

расчете); текст программы, структурная схема программы и результаты расчета

(при проведении расчетов с помощью ПЭВМ).

2.Исходный граф и длина ребер.

3.Таблица итераций.

28

29

Таблица 3.2

30