- -, . . - ( ). - - - . ( ). : - , - . , .
: : RIP, BGP, OSPF; : EIGRP.
. : .
. 1 . , , , .
:
, .
, ( ).
.
: ( , ) , .
: , - .
(-, ): ( (: - )), ( ), ( - , ), .
: y - 2 - x - 1 - z - 7 - y
1. : (.) DX(*, V) = INF, DX(V, V) = C(X, V). minWD(Y, W).
2. : ( , )
. (X, V) d => . y DX(Y, V) +=d . min =>
. - w y. DX(Y, V) = C(X, V) + newval. min , .
3. - .
|
|
DX | Y | Z | DX | Y | Z | |
Y | INF | Y | ||||
Z | INF | Z | ||||
DY | X | Z | DY | X | Z | |
X | INF | X | ||||
Z | INF | Z | ||||
DZ | X | Y | DZ | X | Y | |
X | INF | X | ||||
Y | INF | Y |
3
, , .
: 1) : : > N = INF; 2) ( ) ; 3) .
: ( 1 , , ) : , - .