' G ( ) . . , 2,..., , G.
=1, 2,..., n-1 j=i+1,...,n , j. , G. , .
"" "j"
(i-1, xi), (x, xi+1), (xj-1, xj), (xj, xj+1)
(i-1, xj), (xj, xi+1), (xj-1, xi), (xi, xj+1)
,
- ( );
- , .
, , .
, ' , .
- , . , .
: ( ) () ().
.
: B , , ( , , , , , ).
г: ( - "" ), , () - , () (, ) . () , B.
: G=(V,E) (). s t (s ¹ t).
|
|
|
:
1. vi - : d(s)=0, d(vi)=+_ vi¹s;
2. , s, , s - ;
3. s (c:=s);
4. () .
:
1. uj, , , : d(uj):=min{d(uj), d(c)+Weight(,uj)} (*), (,uj) - (), uj, Weight(,uj) - ; ;
2. +_, ; ղ(" ");
3. ( , , (1)!) x , , () (c',x), , d(x)= d(')+Weight(c',x), c'= ' - , (c'=, (1) uj=x (*)), (c:=x);
4. c=t, d(t), : s t, (3) () ( , ); ղ(" ");
5. (1).
() . , , , s(s,t) t 1 s t, 2+(-2)=0, .
, .
: .
: (, ', ..) n "" ', , , -, "" ' ( ), , -, ' ' , '.
.
G(X, Y), . (x, y) a(x,y).
. ϳ . . () , , () , . , , , . ( ), ( ). ( ).
|
|
|
, , :
- , , ;
- , , ᒺ , ;
- , , ( ).
, , , , , , . , - , .
