Telegram- 👇 😉
-
. WIKIMERIONET
Merion Mertics , ,

CRM

8

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

    Bellman-Ford
. 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.

,  ,       Bellman-Ford

, (). ( ). 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.