Основы математического моделирования. Псигин Ю.В - 17 стр.

UptoLike

ВУЗ: 

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

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

Рубрика: 

16
Общее правило для нахождения кратчайшего пути в графе с ребрами
единичной длины состоит в том, что каждой вершине x
i
приписывают индекс
i
λ , равный длине кратчайшего пути из данной вершины в конечную.
Приписывание индексов вершинам производится в следующем порядке.
1. Конечной вершине х
0
приписывают индекс 0.
2. Вс ем вершинам, из которых идет ребро в конечную вершину, приписы-
вают индекс 1.
3. Вс ем вершинам, еще не имеющим индексов, из которых идет ребро в
вершину с индексом
i
λ , приписывают индекс
1i +
λ . Этот процесс продолжают
до тех пор, пока не будет помечена начальная вершина. По окончании разметки
индекс у начальной вершины будет равен длине кратчайшего пути. Сам
кратчайший путь находят, двигаясь из начальной вершины в направлении
убывания индексов.
Задача приписывания вершинам графа числовых индексов усложняется,
если ребра графа имеют произвольную длину. Усложнение
вызвано тем, что в
сложном графе путь, проходящий через наименьшее число вершин, зачастую
имеет большую длину, чем некоторые обходные пути. Про цесс приписывания
индексов для такого вида графов заключается в следующем.
1. Каждую вершину x
i
помечают индексом
i
λ . Первоначально конечной
вершине x
0
приписывают индекс .0
0
=λ Для остальных вершин
предварительно полагают ∞=λ
i
(i ≠ 0).
2. Находят такую дугу (х
i
, х
j
), для которой
ij
λ−λ > λ(х
i
, х
j
), и
заменяют индекс
j
λ индексом +λ=λ
′
ij
λ(х
i
, х
j
) <
j
λ . Продолжают этот
процесс замены индексов до тех пор, пока остается хотя бы одна дуга, для
которой можно уменьшить
j
λ .
Большое практическое значение имеет задача о построении графа
наименьшей длины (например, минимизация расстояния, проходимого
тел ежкой с заготовками, или общей длины автомобильных дорог, соединяющих
населенные пункты, и др.). Граф соединения n вершин всегда является деревом.
Следовательно, для соединения n вершин нужно построить (n – 1) ребер.
Граф наименьшей длины можно пос троить по следующему прав илу:
прежде всего
соединяют две вершины с наиболее коротким соединяющим
ребром u
1
. На каждом из следующих шагов добавляют самое короткое из ребер
u
i
, при присоединении которого к уже имеющимся ребрам не образуется цикл.
Если имеется несколько ребер одинаковой длины, выбирают любое из них.
Каждое дерево, пос троенное таким образом, называют экономическим, и длина
его равна сумме длин отдельных ребер.

Страницы