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

UptoLike

ВУЗ: 

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

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

Рубрика: 

22
шине в момент достижения, а вторая компонента укажет на предыдущую вер-
шину кратчайшего пути. Первая компонента будет содержать ∞, а вторая – 0 до
тех пор, пока путь не найден. Вершина, которая стала постоянной, будет выде-
лена. Выполнив шаг 1 алгоритма, получаем граф, изображенный на рисунке
1.50.
Поскольку вершины В и С – смежные с
вершиной А, выполняем шаг 2 и
упорядоченной паре для вершины В присваиваем значение (5, А), а упорядо-
ченной паре для вершины С присваиваем значение (6, А). (Фактически измене-
ния вносятся, тогда и только тогда, когда новые расстояния меньше старых, но
поскольку старые расстояния до вершины В и С равны ∞, в данном случае это
не имеет значения). Выполнив шаг 3, выбираем наименьшее из временных при-
своенных значений. В данном случае это расстояние до вершины А равное 5, и
вершину В (5, А) делаем постоянной. Таким образом, получаем рисунок 1.51.
Рис. 1.50 Рис. 1.51
Возвращаясь к шагу 2, рассмотрим временные вершины С, D, E, F, смеж-
ные с вершиной В. В каждом случае прибавляем расстояние от вершины А к
вершине В к расстоянию от вершины В к данным вершинам. Таким образом,
для вершины С это будет 5 + 3 = 8. Для вершины D имеем 5 + 7 = 12. Для вер-
шины E имеем 5 + 2 = 7. Для
вершины F имеем 5 + 10 = 15. Поскольку новое
расстояние до вершины С не меньше, чем уже присвоенное, упорядоченную
пару С(6, А) оставляем без изменений. Новые расстояния до вершин D, E, F
меньше уже присвоенных, поэтому им задаем значения, которые получены для
пути из вершины В, то есть меняем их на D(12, В), E(7,
В), F(15, В).
Выполнив шаг 3, находим наименьшее из расстояний, присвоенных вре-
менным вершинам, поэтому берем min{6, 12, 15, 7} = 6, и поскольку вершина С
имеет это расстояние делаем вершину С(6, А) постоянной. Таким образом, по-
лучаем рис. 1.52.
Рис. 1.52
D(∞, 0)
7
10
2
4
B(∞, 0)
F(∞, 0)
E(∞, 0)
3
7
6
5
A(0, 0)
C(∞, 0)
2
D(∞, 0)
7
10
2
4
B(5, A)
F(∞, 0)
E(∞, 0)
3
7
6
5
A(0, 0)
C(6, A)
2
D(12, B)
7
10
2
4
B(5, A)
F(15, B)
E(7, B)
3
7
6
5
A(0, 0)
C(6, A)
2

Страницы