我正在研究图论,我对最小生成树和最短路径树之间的联系有疑问.
设G是一个无向连通图,其中所有边都以不同的成本加权.令T为G的MST,并且让T s为某个节点s的最短路径树.是牛逼和牛逼小号保证至少有一项优势？
我相信这并非总是如此,但我找不到反例.有没有人有关于如何找到反例的建议？
algorithm math graph shortest-path minimum-spanning-tree
algorithm ×1
graph ×1
math ×1
minimum-spanning-tree ×1
shortest-path ×1