.
G(V,E) (.1) s t. . s t.
.1
.
.
(s)=(s, +∞); − .
s , .
s:
(1)=(,10); (2)=(,8)
s , 1, 2 .
1:
(3)=(1 , 5)
1 .
2:
(4)=(2 , 8)
2 .
3:
(t)=(3 , 5)
t, .
=5
, s t:
(,1 ,3 , t)
r = 5.
.2
(.2) , .
s:
(1)=(,5); (2)=(,8)
s , 1, 2 .
1:
3 1 .
1 .
2:
(4)=(2 , 8)
2 .
4:
(t)=(4 , 8)
4 . t.
=8
, s t:
(,2 ,4 , t)
r = r+8=13.
.3
.3, .
s:
(1)=(,5)
2 s .
s , 1 .
1.
(2)=(,5)
3 4 1 .
1 , 2 .
2.
(4)=(2 , 2)
2 , 4 .
4.
(t)=(4 , 2)
3 1 .
4 . t.
=2
, s t:
(, 1 , 2 ,4 , t)
r = r+2=15.
.4
.4, .
s:
(1)=(,3)
2 s .
s , 1 .
1.
(2)=(, 3)
3 4 1 .
1 , 2 .
2.
2 .
, r =15, :
|
|
=
.
G = N, , U, .. n + 1 , ( ) ( n). (i; j) , . ( , , .. ). () 0 n.
:1) ; 2) 0 ( ) , ( ) n; 3) , n .
G , , (i, j) : i<j. .
G (), 1. − i M(i) =(j, ), , i, .
1.
0: − M(0) = (0, ), = 0.
k, : k M(k) =(j, ), (.. j).
. , n 0 , 0 n. : . ( .) .
. 1
1 1 : , , .
, , 2. − . .
2.
1., i = 0. G , , i.
2. i = n, , − .
i = i + 1.
3. G , , , i. 2.
. 2.
2 2 : − .
− . − i M(i) =(j, ), , i, . .
|
|
3 ( ).
0. , Q − . : M(0) = (0, ), = 0, .. M(0) = (0,0). Q. − M(i) =(0, ), .. = ( , i 0 , , ).
1. k Q ( i , i Q (i,k), j). k , , − M(k) =(j, ) Q.
, n.
. , .
.
.3.
. 3, .
0.
M(0) = (0,0),
M(i) =(0, ) i = 1,2,,n
Q = {0}
1.
; ;
M(3) =(0, 3)
Q = {0, 3}
; ;
M(2) =(3, 8);
Q = {0, 3, 2}
; ;
Q = {0, 3, 2, 4}
; ;
Q = {0, 3, 2, 4, 1}
;
Q = {0, 3, 2, 4, 1, 5}
.4
4 1 : , , .
, .
1. .
2. .
3. .
4. .
:
1 | 2 | |||||
G1 | G2 | G1 | G2 | |||
(i,j) | (i,j) | (i,j) | (i,j) | |||
1−7 | (7;12) | (6;13) | (7;11) | (7;12) | ||
8−15 | (7;13) | (7;9) | (6;10) | (7;13) | ||
10−18 | (7;11) | (7;10) | (6;11) | (7;11) | ||
1−7 | (6;10) | (6;9) | (6;12) | (6;10) | ||
8−15 | (6;11) | (6;12) | (6;13) | (6;11) | ||
10−18 | (6;12) | (6;13) | (7;9) | (6;12) | ||
1−7 | (6;13) | (7;9) | (7;10) | (6;13) | ||
8−15 | (7;9) | (7;10) | (6;9) | (7;9) | ||
10−18 | (7;10) | (6;9) | (6;12) | (7;10) | ||
1−7 | (6;9) | (7;12) | (6;13) | (6;9) | ||
8−15 | (6;10) | (7;13) | (7;9) | (7;12) | ||
10−18 | (7;13) | (7;11) | (7;10) | (7;13) | ||
1−7 | (7;11) | (6;10) | (7;13) | (7;11) | ||
8−15 | (6;10) | (6;11) | (7;11) | (6;10) | ||
10−18 | (6;11) | (6;12) | (6;10) | (6;11) | ||
1−7 | (6;12) | (6;13) | (6;11) | (6;12) | ||
8−15 | (6;13) | (7;9) | (6;12) | (7;9) | ||
10−18 | (7;9) | (7;11) | (6;13) | (6;9) | ||
1−7 | (7;10) | (6;10) | (7;9) | (7;10) | ||
1−7 | (6;9) | (6;11) | (7;10) | (6;9) | ||
8−15 | (6;12) | (6;14) | (6;9) | (6;12) | ||
10−18 | (6;13) | (6;13) | (7;12) | (6;13) | ||
1−7 | (7;9) | (7;9) | (6;2) | (7;9) | ||
8−15 | (7;10) | (7;10) | (6;4) | (7;10) | ||
10−18 | (6;9) | (7;11) | (6;1) | (6;9) |
|
|
− G , − G . (i,j) − , − .
G − , G − . .