25%

🚀

4

- .

Merion Academy


, . , : Minimum Spanning Tree - MST Shortest Path Tree - SPT. . , 3, MST SPT.

3 , , :

  1. [A, B, E, D, C] [A, C, D, E, B], 10
  2. [A, B, E] 5 [A, C, D] 3, 8
  3. [A, C, D, E] 6 [A, B] 1, - 7

MST - , ( , ).

Minimum Spanning Tree  Shortest Path Tree

, MST, 3, , .

SPT , . , SPT, A :

  • [A, B] B 1, , [A, C, D, E, B] 10
  • [A, B, E] E 5, , [A, C, D, E] 6
  • [A, C] C 1, , [A, B, E, D, C] 10
  • [A, C, D] D 3, , [A, B, E, D] 8

, , , SPT, 2, 3 . , SPT MST, ( ), MST , .

SPT, MST, - greedy . SPT , , , , , MST, , .


Greedy

Greedy . , Greedy ( ) , ( ). , , Greedy , .

Greedy . , , . , , , , . Greedy , , .

, , .

- .


>