CODEWITHSUNDEEP
data-structures
pankaj
pankaj

Reputation: 159

What is the difference between Minimum Spanning Tree (MST) and All Pairs Shortest Path (APSP)?

What is the difference between Minimum Spanning Tree (MST) and All Pairs Shortest Path (APSP)? Also is there any real world problem using which the difference between them clearly visible?

Upvotes: 1

Views: 314

Answers (1)

nullptr
nullptr

Reputation: 580

Minimum spanning tree (MST) is a tree that connects all nodes of the graph, with the smallest sum of edge weights. The shortest path between two nodes need not be through edges of the MST. For example in this graph:

   4
A ——— B
 \   /
3 \ / 3
   C

the MST would be the edges AC and BC, but the shortest path from A to B is simply the edge AB.

Upvotes: 2

Related Questions