ВУЗ:
Составители:
Рубрика:
Замечание 1
. Алгоритм применим к неориентированным гра-
фам. Достаточно заменить каждое ребро (v
i
,v
j
), имеющее вес w
ij
, на
пару дуг <v
i
,v
j
> и <v
j
,v
i
> того же веса.
Замечание 2
. Алгоритм может быть использован для нахожде-
ния кратчайшего пути в графе, ребрам (дугам) которого не при-
своены веса. Необходимо каждому ребру (дуге) присвоить вес,
равный единице.
Пример 13.1
. Найти расстояние от b до g в графе, изображен-
ном на рисунке.
Таблица значений меток
θ
(v).
1
2
3
6
4
5
b
7
8
7
2
10
4
a
c e
f
d
g
deceb*c
aeceb*c
acab*c
cb*c
b*b
*
gfedcba
5
4
3
2
1
0
итерации
Номер
Таблица значений меток l(v) (постоянные метки вершин обведены).
Номер
итерации
a b c d e
f
g
0
7
0 2
6 0 27
6 0 210 716
6 0 2 10 71416
6 0 2 10 7 12
∞
∞ ∞ ∞ ∞ ∞
∞ ∞ ∞ ∞
∞
∞ ∞
∞
14
d
b
c
a
e
g
Вершина,
получившая пост.
метку на итерации
4
0
1
2
3
5
sto
p
Расстояние D(b,g)=12, путь bcedg.
53
Страницы
- « первая
- ‹ предыдущая
- …
- 51
- 52
- 53
- 54
- 55
- …
- следующая ›
- последняя »
