Графы и сети. Харитонова Е.В. - 22 стр.

UptoLike

ВУЗ: 

УлГТУ | Ульяновск

Составители: 

Рубрика: 

21
лее находим расстояние от вершины υ
i
до каждой вершины смежной к υ
i
вдоль
пути, проходящего через вершину υ
i
. Если это расстояние меньше, чем текущее
расстояние, присвоенное каждой из вершин, то заменяем им текущее расстоя-
ние. Снова выбираем вершину, ближайшую к υ
i
, но не совпадающую с выбран-
ной ранее, и процесс повторяется.
Алгоритм Дейкстры
Для данного взвешенного графа алгоритм дает кратчайшее расстояние от
вершины υ
1
к вершине υ
n
. Каждой вершине поставим в соответствие упорядо-
ченную пару (∞; 0). Первая координата вершины υ
i
(m, υ
r
) будет означать при-
своенное расстояние от вершины υ
1
к вершине υ
i
, а вторая координата – преды-
дущую вершину пути от υ
1
к υ
i
.
1. Начать в вершине υ
1
(∞; 0), заменить ее на υ
1
(0, 0)
и сделать постоянной.
Остальные вершины на этот момент оставить временными.
2. Когда вершина υ
k
(m, υ
r
)
станет постоянной, для каждой вершины υ
j
смежной к υ
k
прибавить величину m к расстоянию от вершины υ
k
к вершине υ
j
.
Если это значение меньше, чем текущее расстояние, присвоенное вершине υ
j
,
заменить текущее расстояние этой суммой и заменить вторую координату на υ
k
.
3. Найти минимум из расстояний, приписанных временным вершинам.
Первую из вершин с таким расстоянием делаем постоянной.
4. Если υ
n
– не постоянная вершина, то возвращаемся к п.2.
5. Если υ
n
– постоянная вершина, то расстояние, присвоенное вершине υ
n
является кратчайшим расстоянием от υ
1
к υ
n
.
6. Для нахождения пути начать в вершине υ
n
, найти предшествующую ей
вершину пути (вторая координата). Для каждой вершины пути υ
j
находить
предшествующую ей вершину пути, пока не будет достигнута вершина υ
1
. Пе-
рестановка вершин в обратном порядке даст кратчайший путь.
Пример. Пусть граф изображенный на рисунке 1.48 – взвешенный граф, в котором
отыскивается кратчайшее расстояние от вершины А к вершине F. Поставив в соответствие
каждой вершине упорядоченную пару (∞; 0) рассматриваемый граф приводим к виду, пока-
занному на рис. 1.49.
Рис. 1.48 Рис. 1.49
Приступим к построению путей от вершины А к другим вершинам. Пер-
вая компонента упорядоченной пары покажет длину кратчайшего пути к вер-
C
D
F
E
A
B
7
10
2
3
5
6
7
4
2
D(∞, 0)
7
10
2
4
B(∞, 0)
F(∞, 0)
E(∞, 0)
3
7
6
5
A(∞, 0)
C(∞, 0)
2

Страницы