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

UptoLike

ВУЗ: 

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

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

Рубрика: 

20
быть самый дешевый путь, самый безопасный путь, кратчайший путь или тот,
который требует минимум энергии, или путь, выбранный в соответствии с ка-
ким-то иным критерием. Для определения наилучшего пути присвоим каждому
ребру вес или меру. Если пытаться найти кратчайшее расстояние между двумя
городами, то их необходимо предоставить в виде вершин
, а вес, присвоенный
ребрам – это расстояние между городами. Если пытаться найти самый дешевый
способ перелета из одного города в другой, то вес ребра между вершинами
будет стоимостью перелета из города в город. Если прямого перелета между
городами нет, то не будет ребра между соответствующими вершинами. Хотя
вес или мера, присвоенные
ребрам, могут иметь различные значения, для уп-
рощения будем рассматривать вес ребра как расстояние, а наилучший путь из
точки А в точку В как кратчайший путь между точками А и В. Предполагаем,
что вес или мера, названные теперь расстоянием, и приписываемые ребрам ме-
жду двумя различными точками, положительные.
В дальнейшем будем
использовать символ ∞. Для упрощения рассмотре-
ния предположим, что все целые числа меньше ∞, так что min (a, ∞) = a для ка-
ждого неотрицательного целого числа, а min (∞, ∞) = ∞. Примем также, что а +
∞ = ∞ + ∞ = ∞. Это для удобства обозначений.
● Пусть А = (а
1
, а
2
, а
3
, …, а
n
) и В = (b
1
, b
2
, b
3
, …, b
n
) – матрицы – строки,
где каждое из а
i
и b
i
– неотрицательные целые числа или ∞. Тогда
А ∧ В = (min(а
1
, b
1
), min(а
2
, b
2
), min(a
3
, b
3
), … , min(а
n
b
n
))
● Пусть с – число, а A = (а
1
, а
2
, а
3
, …, а
n
) – матрица – строка. Тогда
с + А = с + (а
1
, а
2
, а
3
, … , а
n
) = (с + а
1
, с + а
2
, с + а
3
, … , с + а
n
)
Рассмотрим алгоритм Дейкстры. Этот алгоритм позволяет определить не
только длину кратчайшего пути, но и сам путь. Это достигается с помощью
указателя, который для каждой вершины из кратчайшего пути указывает пре-
дыдущую вершину пути. Таким образом, если найдена длина кратчайшего пути
между А и В, то двигаясь вдоль кратчайшего пути в обратном
направлении от В
к А можно найти сам путь.
ТЕОРЕМА 1.15. Пусть а = υ
1
и b = υ
n
. Если υ
1
, υ
2
, …, υ
i
, υ
i+1, …,
υ
j,
υ
j+1,
…,
υ
n
есть кратчайший путь между а и b, то υ
i
, υ
i+1,
…, υ
j
– часть этого пути между
вершинами υ
i
и
υ
j
является кратчайшим путем между υ
i
и
υ
j.
Начнем с формулировки алгоритма Дейкстры, а затем рассмотрим при-
меры его использования. Согласно алгоритму отыскивается кратчайшее рас-
стояние от вершины υ
1
к вершине υ
n .
Начинаем с вершины υ
1
и находим рас-
стояние от
υ
1
до каждой из смежных с ней вершин. Выбираем вершину, рас-
стояние от которой до вершины υ
1
наименьшее, пусть это будет вершина υ
i
. да-

Страницы