.


:




:

































 

 

 

 





.

. - .

, . . , .

.

1. , .

2. N-1 .

3. N-1 .

4. .

5. .

6. .

3 6. .

, . - , , . . , - , . . - ( ) - / . ( ).

: D [ v ] s vV, t, , A [ u, v ], u, vV. -: - - , - - s t. Begin CTEK:= ; CTEK  t; v:= t;while vs dobegin u:= , D [ v ] = D [ u ] + A [ u, v ]; CTEK  u; v:= u endend.

 

37. 2 :

1. ;

2. .

38. :

s - t - . I(Xi).

1. I(s) = 0, I(Xi) i s . = s.

2. i, () , :
I(Xi) = min[I(Xi), I(p) + c(p, Xi)]

3. , I(Xi*) = min[I(Xi)]

4. i* = i*.

5. =t,I() - - , , 2.

39. .

G, : S T, Cu,v. F , , . .. - Fu, v, .

. -, O (N M2), ( ) O (F M), F - . 1972 .

. , , ( ), , , . -, - , - ( F, -F).

- . . , .. S T , . , . , . , .

. , C - . : (u, v) : Fu, v += C, Fv, u = - Fu, v (, , Fv, u -= C).

FS, v, v - , .

.

- , .

.

y1yk , . . . x1xk . - . - .

, . 1 . 1 . , , .. . , ( ) .

5 5 n=55=3125

. , .. min - , .





:


: 2016-10-27; !; : 707 |


:

:

.
==> ...

1036 - | 889 -


© 2015-2024 lektsii.org - -

: 0.01 .