Bellman-Ford - , . , , - . , , . 7 .

. Bellman-Ford , , Routing Information Protocol (RIP), , , . - .
Bellman-Ford
Bellman-Ford Shortest Path Tree O (V * E), V - () , E - (). , , , Bellman-Ford Shortest Path Tree, . , . 4 .
, Bellman-Ford , . , Bellman-Ford O(E), . , , Shortest Path Tree, - O(V * E) O(E).
Bellman-Ford - greedy , , , , , . , , , , .
, Shortest Path Tree, , . , , , , , , , , .
Bellman-Ford , , 1.

, (). ( ). 7 , SPT 1, 1, , . :
// , // 1, // 2 . . define route[nodes] { predecessor // cost // } // () 0 // 1 - . route[1].predecessor = NULL route[1].cost = 0 // 1, , topo // () // () , i = nodes while i > 0 { j = 1 while j <= nodes { // table source_router = topo[j].s destination_router = topo[j].d link_cost = topo[j].cost if route[source_router].cost == NULL { source_router_cost = INFINITY } else { source_router_cost = route[source_router].cost } if route[destination_router].cost == NULL { destination_router_cost = INFINITY } else { destination_router_cost = route[destination_router].cost } if source_router_cost + link_cost <= destination_router_cost { route[destination_router].cost = source_router_cost + link_ cost route[destination_router].predecessor = source_router } j = j + 1 //or j++ depending on what pseudocode this is representing } i = i - 1 }
, . if route [topo [j] .s] .cost + topo [j] .cost route [topo [j] .d] .cost. . ( , ):
- topo-:
- j 1, topo[j] .s - 6 (F),
- j 1, topo[j] .d - 7 (G), .
- route[6].cost = infinity, topo[1].cost = 1, and route[7].cost = infinity ( infinity - )
- infinity + 1 == infinity,
- topo- infinity , infinity + , infinity. , infinity, .
- topo- ( ):
- j 8, topo[j].s - 1 (A),
- j 8, topo[j].d - 2 (B), .
- route [1].cost = 0, topo[8].cost=2 route[2].cost = infinity.
- 0 + 2 = infinity,
- route[2].predecessor 1, route [2].cost 2
- topo - ( ):
- j 9, topo[j].s - 1 (A),
- j 9, topo[j].d - 3 (C), .
- route[1].cost=0, topo[9].cost=1 route[3].cost = infinity.
- 0 + 1 = infinity,
- route[3].predecessor 1, route[3].cost 1
:
- topo- ( ):
- j 5, topo[j].s - 2 (B),
- j 5, topo[j].d - 6 (F), .
- route[2].cost=2,topo[5].cost=1 route[6].cost = infinity.
- 2 + 1 = infinity,
- route[6].predecessor 2, route[6].cost 3
topo - ( ):
- j 6, topo[j].s 2 (B),
- j 6, topo[j].d 5 (E),
- route[2].cost=2, topo[6].cost=2 route[5].cost = infinity.
- 2 + 2 = infinity,
- route[5].predecessor 2, route[5].cost 4
- 2.
8 , . topo - ( ):
- j 2, topo[j].s - 5 (E),
- j 2, topo[j].d - 8 (H),
- route[5].cost=4, topo[2].cost=1 route[8].cost = infinity.
- 4 + 1 = infinity,
- route[8].predecessor 5, route[8].cost 5
topo - ( ):
- j 3, topo[j].s - 4 (D),
- j 3, topo[j].d - 8 (H),
- route[4].cost=2,topo[3].cost=2 route[8].cost = 5.
- 2 + 2 = 4,
- route[8].predecessor 4, route[8].cost 4
topo- , [5,8] , 8 (H) 5 5. topo [4,8], 8 . 2 topo.

2 , . , A (1) A, B (2) B . . P , A , . C . , , . , , 8 ( ).
DUAL.