New answers tagged

3 votes

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$.
user avatar
  • 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 ...
user avatar
  • 1

Top 50 recent answers are included