Spa*_*cus 12 algorithm math graph shortest-path minimum-spanning-tree
我正在研究图论,我对最小生成树和最短路径树之间的联系有疑问.
设G是一个无向连通图,其中所有边都以不同的成本加权.令T为G的MST,并且让T s为某个节点s的最短路径树.是牛逼和牛逼小号保证至少有一项优势？
我相信这并非总是如此,但我找不到反例.有没有人有关于如何找到反例的建议？
tem*_*def 6
我认为这句话实际上是正确的,所以我怀疑你能找到一个反例.
这是一个提示 - 获取图中的任何节点并找到该节点的最短路径树.现在考虑一下如果从该节点开始运行Prim的算法会发生什么- 你能保证MST中至少有一条边可以进入最短路径树吗？
希望这可以帮助!
归档时间：
12 年，11 月 前
查看次数：
3753 次
最近记录：