New answers tagged minimum-spanning-tree
3
votes
Accepted
Does a minimum spanning tree necessarily provide the lowest cost path between any 2 nodes?
Yes, MSTs usually don't contain the shortest path for any pair of nodes. The simplest example is probably just the MST of 3 nodes connected to each other all with edge weight $1$.
- 1,188
0
votes
safe edge for Minimum spanning tree
I think the issue you having is the understanding of why A respects the cut, and you think that if (u,v) crosses the cut, then A is no longer a valid condition. In the proof when A respects the cut it ...
- 1
Top 50 recent answers are included