- -, . . - ( ). - - - . ( ). : - , - . , .
: : RIP, BGP, OSPF; : EIGRP.
. : .
. 1 . , , , .
: , .
, ( ).
.
: ( , ) , .
: , - .
:
(Link State, ):
3 5
2 5
3
2 1 F
1 2
D E
c(i,j) - i j
D(V) - V - V.
p(V) - V
N - - .
1.
N={A}; V: V , D(V) = C(a,V), p(V)=A) D(v)=
2. N
W N .. D(w) min
w N, D(V), V w
D(V) = min(D(V), D(W)+C(W,V))
N | D(B), p(B) | D(C), p(C) | D(D), p(D) | D(E), p(E) | D(F), p(F) |
A | 2,A | 5,A | 1,A | INF | INF |
A,D | 2,A | 4,D | 1,A | 2,D | INF |
A,D,E | 2,A | 3,E | 1,A | 2,D | 4,E |
A,D,E,B | 2,A | 3,E | 1,A | 2,D | 4,E |
. .
, , ().
: 1) : : > N = INF; 2) ( ) ; 3) .
: ( 1 , , ) : , - .