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$.
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 ...
Top 50 recent answers are included
Related Tags
minimum-spanning-tree × 228graphs × 168
algorithms × 79
weighted-graphs × 41
spanning-trees × 34
trees × 19
prims-algorithm × 15
shortest-path × 12
graph-traversal × 11
time-complexity × 9
greedy-algorithms × 8
correctness-proof × 8
computational-geometry × 5
complexity-theory × 4
algorithm-analysis × 4
traveling-salesman × 4
optimization × 3
np-complete × 3
runtime-analysis × 3
np-hard × 3
distributed-systems × 3
integer-programming × 3
euclidean-distance × 3
depth-first-search × 3
data-structures × 2