Дискретная математика
.pdf
Искомый кратчайший путь:
v0 → . . . → vjl → vjk → . . . → vjs → vn,
его длина равна λ(vn).
Пример 11.1. Найти кратчайший путь из вершины v0 в вершину v5 в графе, заданном рисунком.
v0 |
2 |
v2 |
|
2 |
v4 |
||
|
s |
@s |
|
|
s |
||
1 |
3 |
@ |
@4 |
|
|||
|
2 |
|
|
1 |
|||
|
|
|
|
|
@@ |
@ |
|
v |
s1 |
4 |
vs3 |
|
3 |
v |
s5 |
Решение.
I Прямой ход (нахождение длины кратчайшего пути).
1.
v0 v1 v2 v3 v4 v5
∞ ∞ ∞ ∞ ∞ ∞
Всем |
вершинам |
v0, v1, . . . , v5 |
графа |
ставим в |
соответствие |
метку, равную "∞\.
2.Вершине v0 приписываем метку 0, метки остальных вер-
шин по-прежнему равны "∞\. Вершина v0 - постоянная, все остальные вершины - временные.
Для наглядности постоянные вершины помечаем в таблице и на графе.
|
|
|
|
|
|
|
|
|
|
|
|
|
|
v0 |
|
|
|
s |
@ |
|
|
s |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
s |
|
|
|
|
||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
0l |
2 |
|
v2 |
|
2 |
v4 |
|||
|
v0 |
|
v1 |
|
v2 |
|
v3 |
|
v4 |
|
v5 |
|
@ |
|
|
|
|
||||||
|
|
|
|
|
|
1 |
|
3 |
|
2 |
|
@4 |
|
1 |
|||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||
|
∞ |
|
|
|
∞ |
|
∞ |
|
∞ |
|
∞ |
|
∞ |
|
|
|
|
|
|
|
@@ |
@ |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||||
|
0 |
|
|
|
∞ |
|
∞ |
|
∞ |
|
∞ |
|
∞ |
v |
s1 |
4 |
|
vs3 |
|
3 |
v |
s5 |
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||||||
201
3.Вершинам v1 и v2, смежным с v0, задаем метки, равные длинам ребер.
v0 v1 v2 v3 v4 v5
∞ ∞ ∞ ∞ ∞ ∞
0 ∞ ∞ ∞ ∞ ∞
− 1 2 ∞ ∞ ∞
Вершина v1 имеет наименьшую среди всех вершин метку, равную 1 (вершина v0 уже не рассматривается), и становится постоянной.
v0 |
|
|
s |
|
|
s |
||
|
s |
|
|
|
|
|||
0l |
2 |
v2 |
2 |
v4 |
||||
@ |
|
|
||||||
|
|
|
||||||
1 |
|
3 |
2 |
@@4 |
|
1 |
||
vl |
|
|
|
@@@ |
|
|||
4 |
vs3 |
3 |
vs5 |
|||||
1s |
||||||||
1 |
|
|
|
|
|
|
||
4.Проверим метки у вершин v2 и v3, смежных с постоянной вершиной v1.
Так как λ(v2) = 2, λ(v1) + l(v1, v2) = 1 + 3 = 4 > 2 = λ(v2), то у вершины v2 метку, равную 2, оставляем без изменений. Поскольку λ(v3) = ∞, λ(v1) + l(v1, v3) = 1 + 4 = 5 < ∞ = λ(v3), то величину метки вершины v3 уменьшаем: λ(v3) = λ(v1) + l(v1, v3) = 1 + 4 = 5. Наименьшую метку среди всех вершин имеет вершина v2, которая становится постоянной.
v0 |
v1 |
|
v2 |
v3 |
v4 |
v5 |
|
|
Вершины v0 и v1 ранее |
|||||||
∞ |
∞ |
∞ |
∞ |
∞ |
∞ |
|
|
получили |
свои постоян- |
|||||||
0 |
∞ |
∞ |
∞ |
∞ |
∞ |
|
|
ные метки и из дальней- |
||||||||
− |
1 |
2 |
|
∞ |
∞ |
∞ |
|
|
шего |
рассмотрения ис- |
||||||
− |
− |
|
2 |
|
5 |
∞ |
∞ |
|
|
ключаются. |
||||||
|
|
|
|
|
|
v0 |
|
|
|
v2 |
@ |
|
|
s |
||
|
|
|
|
|
|
|
s |
|
|
|
s |
|
|
|||
|
|
|
|
|
|
|
|
|
|
2 |
2 |
|
2 |
v4 |
||
|
|
|
|
|
|
0l |
|
|
|
@l |
|
|
|
|||
|
|
|
|
|
|
1 |
|
|
|
3 |
2 |
|
@4 |
|
1 |
|
|
|
|
|
|
|
1ls |
|
vs3 |
|
@@ |
|
s5 |
||||
|
|
|
|
|
|
|
4 |
|
3 v |
|||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
@ |
|
|
|
|
|
|
|
|
v1 |
|
|
|
|
|
|
|
|
||
202
5.Исследуем метки вершин v3, v4 и v5, смежных с постоянной вершиной v2. Вершина v1, несмотря на то, что также смежна с v2, более не рассматривается.
λ(v3) = 5, λ(v2) + l(v2, v3) = 2 + 2 = 4 < 5 = λ(v3),
значит, метку уменьшаем:
λ(v3) = λ(v2) + l(v2, v3) = 2 + 2 = 4;
λ(v4) = ∞, λ(v2) + l(v2, v4) = 2 + 2 = 4 < ∞ = λ(v4).λ(v4) = 4;
λ(v5) = ∞, λ(v2) + l(v2, v5) = 2 + 4 = 6 < ∞ = λ(v5),
λ(v5) = 6.
Внашей таблице две вершины имеют метку, равную 4. В качестве постоянной можно выбрать любую из этих вершин. Выберем вершину, расположенную в таблице левее, то есть вершину v3.
v0 |
v1 |
v2 |
|
v3 |
v4 |
v5 |
v0 |
|
v2 |
|
|
s |
|||||
|
|
|
|
|
|
|
|
|
s |
|
|
s |
|
|
|||
∞ |
∞ |
∞ |
∞ |
∞ |
∞ |
l |
2 |
@l |
2 |
v4 |
|||||||
|
|
|
|
|
|
|
|
0 |
|
|
2 |
|
|
|
|||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
0 |
∞ |
∞ |
∞ |
∞ |
∞ |
1 |
|
|
3 |
@@4 |
|
|
|
||||
|
|
|
|
|
1 |
||||||||||||
− |
1 |
2 |
∞ |
∞ |
∞ |
|
|
|
|
|
2 |
@ |
|
|
|||
− |
|
|
|
|
|
|
@@ |
|
|
||||||||
− |
2 |
5 |
|
∞ |
∞ |
|
|
|
|
|
|
|
|
||||
|
|
|
|
|
|
|
|
1 |
|
s |
|
4s |
3 v |
|
s5 |
||
|
|
|
|
4 |
|
4 |
6 |
|
4 |
|
|||||||
|
|
|
|
|
|
||||||||||||
− |
− |
− |
|
|
|
|
|
vl |
|
vl |
|
|
|
|
|||
|
|
|
|
|
|
|
|
|
1 |
|
3 |
|
|
|
|
||
6.Вершина v5 смежна с v3 (остальные смежные с v3 вершины уже постоянны).
λ(v5) = 6, λ(v3) + l(v3, v5) = 4 + 3 = 7 > 6 = λ(v5);
метка λ(v5) остается без изменений.
v0 |
v1 |
v2 |
v3 |
|
v4 |
v5 |
|
∞ |
∞ |
∞ |
∞ |
∞ |
∞ |
||
0 |
∞ |
∞ |
∞ |
∞ |
∞ |
||
− |
1 |
2 |
∞ |
∞ |
∞ |
||
− |
− |
2 |
5 |
∞ |
∞ |
||
− |
− |
− |
4 |
4 |
|
6 |
|
− |
− |
− |
− |
|
4 |
|
6 |
|
|
|
|
|
|
|
|
v0 |
|
v2 |
|
|
v4 |
||||
l |
|
@l |
|
|
s |
l |
|||
0 |
s |
2 |
|
s |
|
2 |
|
|
|
|
2 |
|
4 |
||||||
1 |
|
3 |
|
2 |
@@4 |
|
1 |
||
vl |
|
v |
l |
@@ |
@ |
|
|
||
1 |
s |
4 |
4s |
|
3 |
s5 |
|||
|
v |
||||||||
|
1 |
|
3 |
|
|
|
|
|
|
203
7. λ(v5) = 6, λ(v4) + l(v4, v5) = 4 + 1 = 5 < 6 = λ(v5),
λ(v5) = 5.
Вершина v5 стала постоянной, получив метку λ(v5) = 5, равную длине кратчайшего пути из v0 в v5.
v0 |
v1 |
v2 |
v3 |
v4 |
|
v5 |
|
∞ |
∞ |
∞ |
∞ |
∞ |
∞ |
||
0 |
∞ |
∞ |
∞ |
∞ |
∞ |
||
− |
1 |
2 |
∞ |
∞ |
∞ |
||
− |
− |
2 |
5 |
∞ |
∞ |
||
− |
− |
− |
4 |
4 |
6 |
|
|
− |
− |
− |
− |
4 |
6 |
|
|
− |
− |
− |
− |
− |
|
5 |
|
|
|
|
|
|
|
|
|
v0 |
|
v2 |
|
|
v4 |
|||||
l |
|
@l |
|
|
s |
l |
||||
0 |
s |
2 |
s |
|
2 |
|
|
|||
|
|
2 |
|
4 |
||||||
1 |
|
|
3 |
2 |
@@4 |
|
|
1 |
||
|
|
s |
|
4s |
|
@ |
@@ |
|
s5 |
|
1 |
|
4 |
|
3 |
|
|||||
|
|
|
||||||||
vl |
|
vl |
|
v l |
||||||
|
1 |
|
3 |
|
|
5 |
||||
Прямой ход алгоритма завершен.
IIОбратный ход (нахождение кратчайшего пути).
1.Вершина v5 смежна с тремя вершинами v2, v3, v4. Проверим, для какой из вершин выполнено равенство
λ(v5) − λ(vi) = l(v5, vi).
v2: λ(v5) − λ(v2) = 5 − 2 = 3 ≠ 4 = l(v5, v2); v3: λ(v5) − λ(v3) = 5 − 4 = 1 ≠ 3 = l(v5, v3); v4: λ(v5) − λ(v4) = 5 − 4 = 1 = l(v5, v4).
Так как только для вершины v4 равенство верно, она входит
|
1 |
|
|
|
|
|
|
|
||
в кратчайший путь: v5 → v4. |
|
|
|
|
|
|
|
|||
v0 |
|
v2 |
|
|
v4 |
|||||
l |
|
@l |
|
|
s |
l |
||||
0 |
s |
2 |
s |
|
2 |
|
|
|||
|
|
2 |
|
4 |
||||||
1 |
|
|
3 |
2 |
@@4 |
|
|
|
1 |
|
|
|
s |
|
4s |
|
@ |
@@ |
|
s |
|
1 |
|
|
|
|
|
|
||||
|
4 |
|
3 |
|
5 |
|||||
vl |
|
vl |
|
v l |
||||||
|
1 |
|
3 |
|
|
5 |
||||
204
2.Только вершина v2 смежна с вершиной v4, для неё разность меток концов ребра равна длине ребра:
λ(v4) − λ(v2) = 4 − 2 = 2 = l(v4, v2).
|
|
|
|
1 |
|
|
2 |
|
|
|
|
|
|
|
|
|
|
|
v5 → v4 → v2. |
|
|||||||||||
|
v0 |
|
v2 |
|
|
v4 |
|||||||||
|
l |
|
@l |
|
|
|
|
|
|
s |
l |
||||
|
|
s |
2 |
s |
|
2 |
|
|
|
|
|
|
|||
|
0 |
|
|
|
2 |
|
|
|
|
|
|
|
4 |
||
|
1 |
|
|
3 |
2 |
@@4 |
|
|
|
|
|
|
1 |
||
|
|
|
s |
|
4s |
|
@ |
@@ |
|
|
|
|
|
s5 |
|
|
1 |
|
4 |
|
3 |
|
|
|
|
|
|||||
|
|
|
|
|
|
||||||||||
|
vl |
|
vl |
|
v l |
||||||||||
|
|
1 |
|
3 |
|
|
5 |
||||||||
3. Вершины v0, v1 и v4 смежны с вершиной v2. |
|||||||||||||||
v0: |
λ(v2) − λ(v0) = 2 − 2 = 0 = l(v2, v0); |
||||||||||||||
v1: |
λ(v2) − λ(v1) = 2 − 1 = 1 ̸= 3 = l(v2, v1); |
||||||||||||||
v3: |
λ(v2) − λ(v3) = 2 − 4 = −2 ̸= 2 = l(v2, v3). |
||||||||||||||
Вершина v0 входит в кратчайший путь: |
|
||||||||||||||
|
|
|
|
1 |
2 |
|
2 |
|
|
|
|
|
|
|
|
|
|
v5 → v4 |
→ v2 → v0. |
|
|||||||||||
|
v0 |
|
v2 |
|
|
v4 |
|||||||||
|
l |
|
@l |
|
|
|
|
|
|
s |
l |
||||
|
|
s |
2 |
s |
|
2 |
|
|
|
|
|
|
|||
|
0 |
|
|
|
2 |
|
|
|
4 |
||||||
|
1 |
|
|
3 |
2 |
@@4 |
|
|
|
|
|
|
1 |
||
|
|
|
s |
|
4s |
|
@ |
@@ |
|
|
|
|
|
s5 |
|
|
1 |
|
4 |
|
3 |
|
|
|
|
|
|||||
|
|
|
|
|
|
||||||||||
|
vl |
|
vl |
|
v l |
||||||||||
|
|
1 |
|
3 |
|
|
5 |
||||||||
Ответ: Кратчайший путь из вершины v0 в вершину v5: v0 → v2 → v4 → v5,
его длина равна 5.
Пример 11.2. Найти кратчайший путь из вершины v0 в вершину v5 в графе, заданном рисунком.
205
|
v1 |
|
4 |
v3 |
|
||
2 @s |
|
@s |
|
||||
@3 |
|
@1 |
|||||
|
1 |
@ |
|
|
|
@ |
|
|
|
|
|
@ |
|
|
@ |
v0 s@@ |
|
|
3 @@ |
2 |
2 sv5 |
||
4@@ |
s |
6 |
@@ |
s |
|||
v2 v4
Решение.
IПрямой ход (нахождение длины кратчайшего пути).
1.Как в предыдущем примере, метки вершин будем перечислять в таблице:
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Всем |
|
|
|
|
вершинам |
|
|||||
|
|
v0 |
|
|
v1 |
|
v2 |
|
v3 |
|
v4 |
|
v5 |
v0, v1, . . . , v5 |
|
графа |
|
||||||||||||
|
∞ |
|
∞ |
|
∞ |
|
∞ |
|
∞ |
|
∞ |
ставим |
|
в соответствие |
|
||||||||||||||
2. |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
метку, равную "∞\. |
|
|
|
||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
v1 |
|
|
4 |
v3 |
|
|
|
||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2 @s |
|
@s |
|
|
|
|||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
@3 |
|
@1 |
|
|
||||||
|
|
v0 |
|
|
v1 |
|
v2 |
|
v3 |
|
v4 |
|
v5 |
0 |
|
1 |
|
@ |
|
|
@ |
|
|
||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
@ |
2 |
|
@ |
|
||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
v0l@ |
|
|
|
|
|
@ |
|
v5 |
|||
|
|
∞ |
|
|
|
∞ |
|
∞ |
|
∞ |
|
∞ |
|
∞ |
s |
@ |
|
|
|
3 @ |
|
|
2 |
|
s |
||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||||||||||
|
|
0 |
|
|
|
∞ |
|
∞ |
|
∞ |
|
∞ |
|
∞ |
|
4@@ |
|
@@ |
|
|
|||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||||||||||
3. |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
v |
s2 |
|
|
6 |
v |
s4 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
s |
|
|
|
s |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2 |
v1 |
4 |
v3 |
|
|
|
|||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
@l |
|
@ |
|
|
|
||||
|
|
v0 |
|
|
v1 |
|
v2 |
|
v3 |
|
v4 |
|
v5 |
|
2 |
|
@3 |
|
|
@1 |
|
|
|||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||||||||||
|
|
|
|
|
|
|
|
0 |
|
1 |
|
@ |
|
|
@ |
|
|
||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
@ |
2 |
|
@ |
|
||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
v0l@ |
|
|
|
|
|
@ |
|
v5 |
|||
|
∞ |
|
∞ |
|
∞ |
|
∞ |
|
∞ |
|
∞ |
s |
@ |
|
|
|
3 @ |
|
|
2 |
|
s |
|||||||
|
|
0 |
|
|
∞ |
|
|
|
∞ |
|
∞ |
|
∞ |
|
∞ |
|
4@ |
|
@ |
|
|
||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||||||||
|
|
− |
|
|
2 |
|
|
|
4 |
|
∞ |
|
∞ |
|
∞ |
|
|
@ |
s |
|
6 |
@ |
s |
|
|
|
|||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
v2 |
|
|
|
v4 |
|
|
|
||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||
4.λ(v1) + l(v1, v2) = 2 + 1 = 3 < 4 = λ(v2),
λ(v2) = λ(v1) + l(v1, v2) = 2 + 1 = 3.
206
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
s |
|
|
s |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2 |
v1 |
4 |
v3 |
|
|
|
|
|
v |
|
v |
|
|
v |
|
|
v |
|
v |
|
v |
|
|
|
|
@l |
|
@ |
|
|
|
|
||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||||
0 |
1 |
|
2 |
|
3 |
4 |
5 |
|
|
|
|
@ |
|
|
@ |
1 |
|
|
|||||||
|
|
|
|
|
|
|
|
|
s |
2 |
|
3 |
|
|
|
|
s |
||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
1 |
@ |
|
|
|
@ |
|
|||||
0 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||
∞ |
∞ |
∞ |
∞ |
∞ |
∞ |
v0l@ |
2 |
|
v5 |
||||||||||||||||
|
|
|
|
@ |
|
|
|||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
0 |
|
|
|
|
|
@ |
|
|
|
@ |
|
|
|
∞ |
∞ |
∞ |
∞ |
∞ |
|
|
4 |
|
|
3 |
|
|
2 |
|
|
||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
@ |
|
|
|
@ |
|
|
|
|
|
− |
2 |
4 |
|
∞ |
∞ |
∞ |
|
|
|
@@ |
|
6 |
@@ |
|
|
|
|||||||||
|
|
|
3 |
|
|
|
|
|
|
|
|||||||||||||||
− |
− |
|
|
6 |
5 |
∞ |
|
|
|
3s |
v2 |
|
vs4 |
|
|
|
|
||||||||
|
|
|
|
|
|
|
|
|
|
|
|
l |
|
|
|
|
|
|
|||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
5. λ(v2) + l(v2, v3) = 3 + 3 = 6 = λ(v3),
метку λ(v3) оставляем без изменений;
|
|
λ(v2) + l(v2, v4) = 3 + 6 = 9 > 5 = λ(v4); |
|
|
|
|||||||||||||||||
метку λ(v4) оставляем без изменений; |
|
|
|
|
|
|
|
|
||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
2 |
v1 |
4 |
|
v3 |
|
|
|
|
||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||
v0 |
v1 |
v2 |
v3 |
|
v4 |
v5 |
|
|
|
|
@l |
|
|
@ |
|
|
|
|||||
∞ |
∞ |
∞ |
∞ |
∞ |
∞ |
|
|
|
|
|
|
@ |
|
|
||||||||
|
|
|
|
s |
@ |
|
|
s |
@ |
|
|
|||||||||||
|
|
|
|
|
|
|
|
|
s |
2 |
|
@3 |
|
|
|
1 |
|
s |
||||
|
2 |
4 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
0 |
∞ |
∞ |
∞ |
∞ |
∞ |
v0l@ |
|
|
1 |
|
@ |
|
2 |
|
|
v5 |
||||||
|
|
|
|
|
|
|
|
0 |
|
|
|
|
|
|
@ |
|
|
|
|
|
@ |
|
− |
|
|
∞ |
∞ |
∞ |
|
|
4 |
|
|
|
3 |
|
@ |
|
|
2 |
|
|
|||
|
|
|
|
|
|
|
|
|
|
@ |
|
|
|
|
|
|
|
|
|
|
|
|
− |
− |
3 |
6 |
5 |
|
∞ |
|
|
|
@@ |
|
6 |
@@ |
|
|
|
|
|||||
− |
|
|
|
|
|
|
|
|
|
|
||||||||||||
|
|
|
|
|
|
|
|
|
|
|
||||||||||||
− |
− |
6 |
|
5 |
|
∞ |
|
|
|
|
|
l |
|
|
|
l |
|
|
|
|||
|
|
|
|
|
|
|
|
|
|
3s |
v2 |
|
|
5s |
v4 |
|
|
|||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
6. λ(v4) + l(v4, v5) = 5 + 2 = 7 < ∞ = λ(v5), λ(v5) = 7.
|
v0 |
v1 |
v2 |
|
v3 |
v4 |
v5 |
|
|
|
|
|
|
v1 |
|
|
|
|
v3 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2 |
4 |
|
6 |
|
|
|
||||
|
∞ |
∞ |
∞ |
∞ |
∞ |
∞ |
|
|
|
|
@l |
|
|
@l |
|
|
|
||||||
0 |
∞ |
∞ |
∞ |
∞ |
∞ |
|
s |
2 |
|
s |
@3 |
|
|
s |
@ |
1 |
|
s |
|||||
|
|
|
|
|
1 |
@ |
|
|
|
|
@ |
|
|||||||||||
|
|
2 |
3 |
6 |
|
5 |
|
|
|
|
|
|
|
|
|
|
|
|
|||||
|
− |
4 |
∞ |
∞ |
∞ |
v0l@ |
|
|
|
@ |
|
2 |
|
|
v5 |
||||||||
|
|
|
|
|
|
|
|
|
0 |
|
|
|
|
|
|
@ |
|
|
|
|
|
@ |
|
|
− |
− |
|
|
|
|
|
∞ |
|
|
4 |
|
|
|
3 |
@ |
|
|
|
2 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
@ |
|
|
|
|
|
|
|
|
|
|
||
|
− |
− |
− |
6 |
|
5 |
∞ |
|
|
|
@@ |
|
6 |
@@ |
|
|
|
|
|||||
|
|
|
|
− |
|
|
|
|
|
|
|||||||||||||
|
− |
− |
− |
|
6 |
|
7 |
|
|
|
|
|
l |
|
|
l |
|
|
|
||||
|
|
|
|
|
|
|
|
|
|
|
3s |
v2 |
|
|
5s |
v4 |
|
|
|
||||
7. |
|
|
|
λ(v3) + l(v3, v5) = 6 + 1 = 7 = λ(v5), |
|
|
|
|
|||||||||||||||
метку не меняем.
Вершина v5 стала постоянной, получив метку λ(v5) = 7, равную длине кратчайшего пути из v0 в v5.
207
v0 |
v1 |
v2 |
v3 |
v4 |
|
|
v5 |
|
|
|
|
|
|
v1 |
|
|
|
|
v3 |
|
|
|
||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2 |
4 |
|
6 |
|
|
|
||||
∞ |
∞ |
∞ |
∞ |
∞ |
∞ |
|
|
|
|
@l |
|
|
@l |
|
|
|
||||||||
0 |
∞ |
∞ |
∞ |
∞ |
∞ |
|
s |
2 |
|
s |
@3 |
|
|
s |
@ |
1 |
s |
|
||||||
|
|
|
|
1 |
@ |
|
|
|
|
@ |
v5 |
|||||||||||||
|
2 |
3 |
6 |
5 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||
− |
|
|
∞ |
∞ |
∞ |
v0l@ |
|
|
|
|
|
@ |
|
2 |
|
l |
||||||||
|
|
|
|
|
|
|
|
|
|
0 |
|
|
|
|
|
|
@ |
|
|
|
|
@ |
7 |
|
− |
− |
|
|
|
∞ |
|
|
4 |
|
|
|
3 |
@ |
|
|
|
2 |
|
|
|||||
|
|
|
|
|
|
|
|
|
|
|
|
@ |
|
|
|
|
|
|
|
|
|
|
||
− |
− |
− |
6 |
5 |
|
|
∞ |
|
|
|
|
|
@@ |
|
6 |
@@ |
|
|
|
|
||||
|
|
|
|
|
|
|
|
|
|
|||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||||||
− |
− |
− |
− |
− |
|
|
7 |
|
|
|
|
|
|
3s |
v2 |
|
|
5s |
v4 |
|
|
|
||
|
|
|
|
|
|
|
|
|
|
l |
|
|
l |
|
|
|
||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Прямой ход алгоритма завершен.
IIОбратный ход (нахождение кратчайшего пути).
1.Вершина v5 смежна с двумя вершинами v3 и v4. Для обеих вершин равенство λ(v5) − λ(vi) = l(v5, vi) верно:
v3: λ(v5) − λ(v3) = 7 − 6 = 1 = l(v5, v3); v4: λ(v5) − λ(v4) = 7 − 5 = 2 = l(v5, v4). Значит, имеем два кратчайших пути:
1
v5 → v3
|
|
|
2 v1 |
4 |
|
6 v3 |
|
|
|
|||||
|
|
|
|
|
|
|
|
@ |
|
|
|
|||
|
|
|
@l |
|
|
|
|
l |
|
|
|
|||
|
|
2 |
|
s |
@3 |
|
|
|
|
s |
@1 |
|
|
|
0 |
|
|
1 |
@ |
|
|
|
|
|
@ |
|
|
v5 |
|
|
|
|
|
@ |
|
2 |
|
|
@7 |
|
||||
v0l@ |
|
|
|
3 |
@ |
|
|
|
|
s |
l |
|||
|
s |
@ |
|
|
@ |
|
|
|
|
2 |
|
|
||
|
|
4@ |
|
|
|
|
@ |
|
|
|
|
|
|
|
|
|
|
|
l |
6 |
|
|
|
l |
|
|
|
||
|
|
|
|
|
|
|
|
|
||||||
|
|
|
@3sv2 |
|
@5sv4 |
|
|
|
||||||
2
v5 → v4
|
|
|
@l |
|
|
@l |
|
|
||||
|
|
|
2 |
v1 |
4 |
|
6 |
v3 |
|
|
||
|
|
2 |
|
s |
@3 |
|
|
s |
@ |
1 |
|
|
0 |
|
|
1 |
|
@ |
|
|
|
|
@ |
v5 |
|
|
|
|
|
@ |
|
2 |
|
|
@7 |
|
||
v0l@ |
|
|
|
3 |
@ |
|
|
|
l |
|||
|
s |
@ |
|
|
@ |
|
|
|
2 s |
|
||
|
|
4@ |
|
|
|
|
@ |
|
|
|
|
|
|
|
|
|
l |
|
|
|
l |
|
|
||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
@3sv2 |
6 |
|
@5s |
v4 |
|
|
|||
2.Путь 1: вершина v3 смежна с v1,v2,v4 и v5. Для двух вершин (v1 и v2) разность меток равна длине соединяющего их ребра:
λ(v3) − λ(v1) = 6 − 2 = 4 = l(v3, v1)4;
λ(v3) − λ(v2) = 6 − 3 = 3 = l(v3, v2).
Опять получаем два маршрута:
208
|
|
|
1 |
|
4 |
|
|
|
|
|
|
|
|
|
1 |
|
|
3 |
|
|
|
|
|
|
|
|
|
v5 → v3 → v1 (путь 1.1) |
|
|
|
v5 → v3 → v2 (путь 1.2) |
|
|
|
||||||||||||||||||
|
|
|
|
l@ |
|
l |
|
|
|
|
|
|
|
l |
|
|
l |
|
|
|
||||||
|
|
|
|
2 |
v1 |
4 |
6 |
v3 |
|
|
|
|
|
|
2 |
v1 |
4 |
6 |
v3 |
|
|
|
||||
|
|
|
|
|
|
|
|
|
@ |
|
|
|
|
|
|
@ |
|
@ |
|
|
|
|||||
|
|
|
|
|
s |
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||
|
|
2 |
@3 |
|
|
s |
@1 |
|
|
|
|
|
2 |
|
s |
@3 |
s |
@1 |
|
|
|
|||||
0 |
|
|
|
1 |
|
@ |
|
|
@ |
|
|
v5 |
0 |
|
|
1 |
|
@ @ |
|
|
v5 |
|||||
|
|
|
|
|
@ |
2 |
|
@7 |
|
|
|
|
|
@ |
2 |
@7 |
|
|||||||||
v0l@ |
|
|
|
|
|
@ |
|
|
l |
v0l@ |
|
|
|
|
@ |
|
s |
l |
||||||||
|
s |
@ |
|
|
|
3 @ |
|
|
2 |
s |
|
|
|
s |
@ |
|
|
3 @ |
|
|
2 |
|
|
|||
|
|
4@ |
|
|
|
@ |
|
|
|
|
|
|
|
|
4@ |
|
|
|
|
@ |
|
|
|
|
|
|
|
|
|
|
|
l |
|
|
l |
|
|
|
|
|
|
|
l |
|
|
l |
|
|
|
||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
@ |
|
|
|
|
||
|
|
|
|
@3sv2 |
6 |
@5sv4 |
|
|
|
|
|
@3s |
v2 |
6 |
5s |
v4 |
|
|
|
|||||||
|
|
Путь |
2: |
вершина |
v4 |
|
смежна с вершинами v1,v2,v3 |
|||||||||||||||||||
|
|
и |
|
v5. |
Только |
для |
|
вершины |
v1 |
верно |
равенство: |
|||||||||||||||
λ(v4) − λ(v1) = 5 − 2 = 3 = l(v4, v1).
Путь 2 можно продолжить следующим образом:
|
|
|
|
|
|
|
2 |
|
3 |
|
|
|
|
|
|
|
|
|
|
v5 → v4 → v1 |
|
|
|
||||||
|
|
|
|
|
l |
|
|
|
l |
|
|
|||
|
|
|
|
|
2 |
v1 |
4 |
|
6 |
v3 |
|
|
||
|
|
|
|
|
|
@ |
|
|
@ |
|
|
|||
|
|
|
|
2 |
|
s |
@3 |
|
|
|
s |
@1 |
|
|
|
|
|
0 |
|
1 |
|
@ |
|
|
|
@ |
v5 |
|
|
|
|
|
|
|
|
|
@ |
2 |
|
@7 |
|
|
||
|
|
|
v0l@ |
|
|
|
|
@ |
|
l |
|
|||
|
|
|
s |
@ |
|
|
3 |
@ |
|
|
2 s |
|
|
|
|
|
|
|
4@ |
|
|
|
|
@ |
|
|
|
|
|
|
|
|
|
|
|
l |
|
@ |
l |
|
|
|||
|
|
|
|
|
|
|
|
|
|
|
|
|
||
|
|
|
|
|
@3sv2 |
6 |
|
5s |
v4 |
|
|
|||
3. Рассмотрим продолжения полученных путей: |
|
|
||||||||||||
1 |
4 |
2 |
(путь 1.1) |
v5 |
1 |
3 |
|
|
1 |
2 |
(путь 1.2) |
|||
v5 → v3 |
→ v1 |
→ v0 |
→ v3 → v2 → v1 |
→ v0 |
||||||||||
|
|
l@ |
|
|
l |
|
|
|
||||||
|
|
|
2 |
v1 |
4 |
|
6 |
v3 |
|
|
|
|||
|
|
|
|
|
|
|
|
|
|
@ |
|
|
|
|
|
|
|
|
s |
|
|
|
|
|
|
|
|
||
|
2 |
@3 |
|
|
|
|
s |
@1 |
|
|
|
|||
|
|
|
1 |
|
@ |
|
|
|
|
|
@ |
|
|
v5 |
0 |
|
|
|
|
@ |
|
2 |
|
|
@7 |
|
|||
v0l@ |
|
|
|
3 |
@ |
|
|
|
|
s |
l |
|||
s |
@ |
|
|
|
@ |
|
|
|
|
2 |
|
|
||
|
4@ |
|
|
|
|
@ |
|
|
|
|
|
|
|
|
|
|
|
|
l |
6 |
|
|
|
l |
|
|
|
||
|
|
|
|
|
|
|
|
|
||||||
|
|
|
@3sv2 |
|
@5sv4 |
|
|
|
||||||
|
|
l@ |
|
|
l |
|
|
|
|||||
|
|
|
2 |
v1 |
4 |
6 |
v3 |
|
|
|
|||
|
|
|
|
|
s |
|
@ |
|
|
|
|||
|
2 |
|
@3 |
s |
@1 |
|
|
|
|||||
|
|
1 |
|
|
@ |
|
|
|
@ |
|
|
v5 |
|
0 |
|
|
|
|
@ |
2 |
@7 |
|
|||||
v0l@ |
|
|
|
|
@ |
|
s |
l |
|||||
s |
@ |
|
|
|
|
3 |
@ |
|
|
2 |
|
|
|
|
4@ |
|
|
|
|
@ |
|
|
|
|
|
|
|
|
|
|
|
|
l |
|
@ |
l |
|
|
|
||
|
|
|
|
|
|
|
|
|
|
|
|||
|
|
|
@3s |
v2 |
6 |
5s |
v4 |
|
|
|
|||
209
|
2 |
|
|
|
3 |
|
2 |
(путь 2) |
|
||
v5 → v4 |
→ v1 |
→ v0 |
|
||||||||
|
|
|
|
l |
4 |
|
l |
|
|||
|
|
|
2 |
v1 |
|
6 |
v3 |
|
|||
|
|
|
|
|
|
|
|
|
|||
|
|
@ |
|
@ |
|
||||||
|
2 s |
@3 |
|
|
s |
@1 |
|
||||
|
|
1 |
@ |
|
|
|
|
@ |
v5 |
||
0 |
|
|
|
@ |
2 |
@7 |
|
||||
v0l@ |
|
|
|
|
@ |
l |
|||||
s |
@ |
|
|
|
3 |
|
@ |
|
|
2 s |
|
|
4@ |
|
|
|
|
@ |
|
|
|
|
|
|
|
|
|
l |
|
|
l |
|
|||
|
|
|
|
|
|
|
@ |
|
|
||
|
|
|
@3sv2 |
6 |
|
5s |
v4 |
|
|||
Несмотря на то, что мы получили 3 кратчайших пути:
v0 → v1 → v3 → v5,
v0 → v1 → v2 → v3 → v5,
v0 → v1 → v4 → v5,
все они имеют одинаковую длину 7, то есть все являются кратчайшими.
Заметим, что рассматривать все пути нет необходимости, достаточно выбрать любой из них.
Пример 11.3. Найти кратчайший путь из вершины v0 в вершину v9 в графе, заданном рисунком.
|
|
|
v1 |
|
4 |
v4 |
|
2 |
v7 |
|
|
|
|||
|
|
|
|
s |
|
2 @s |
@4 |
|
s@@1 |
||||||
|
3 |
2 |
|
|
|
2 |
|
@ |
|
1 |
|
@ |
|
||
|
|
|
v2 |
|
|
|
|
v5 |
@ |
@ |
v8 |
@ v |
|||
|
|
|
|
|
|
|
@ |
9 |
|||||||
v0 |
s@@ |
1 |
2 |
s@@ |
3 |
|
s |
|
5 |
s |
3 |
s |
|||
|
|
@ |
|
|
@4 |
2 |
|
|
|
|
|
||||
2 |
@ |
|
|
@ |
|
3 |
4 |
|
|
|
|
||||
|
|
|
@ |
|
|
|
@ |
|
|
|
|
|
|
||
|
|
|
v |
s3 |
|
5 |
v |
s6 |
|
|
|
|
|
|
|
Решение.
Заполним таблицу значений меток всех вершин файла:
210