(, ), , . . qij. , qij = 0 , , i j. , , . , , ( , , ). , , , ( , ), , ( ) ( ) . , , , ( ).
t () s () cij, (. . , i j), :
1) cij 0, cij > 0, cji = 0 ( );
2) cij qij ( );
3) i ( ),
. . , i, , ;
4) , t, , s:
t s.
:
t s. , . (), ().
(1955). t s .
(. . , ), .
, t s . . , t s. . , , , . .
|
|
, , .
1. . cij (- , , , cij = 0). , , Y. . ( ) : + ( Y), c , ( ) , .
, Y :
t Y (0,); , , , , ;
i Y cij < qij ( (i,j) ), j Y j (+i, dj), dj >0 dj = min { dj, qij cij }. , di i, + i , , (i, j) ( );
Y cik > 0 ( ), j Y ( , dj), , j , dj = min{ dk, qik + cik }, , dj . , Y , . . Y, Y , .
Y ( ), 2 .
1. (. . s) Y. , Y Z. , Y, Z . Y (. 1).
, Y Z, t s. , ( , ) t s. , ( ), .
.1
2. s Y, d s > 0. , , t s ( ),
. 2
t s
, , , , , . ds cij ( , qij) d s cij ( , qij, ds cij + qij, , ,
|
|
, , cij , , t s ( , (1)(4)). , ds > 0. . .
, , 1 ( ), ( ), , , - , s Y, . . . .
( , ). . (. . ) , . , , , , (, , , ). ( ). , .