运筹学最短路问题
答案:1 悬赏:60
解决时间 2021-03-12 00:59
- 提问者网友：藍了天白赴美
- 2021-03-11 16:30
运筹学最短路问题
最佳答案
- 二级知识专家网友：持酒劝斜阳
- 2021-03-11 17:28
通过最小支撑树来求最短路的想法是不是认为求得了一个图的最小支撑树，则最小支撑树上任意两点间的链就是要求的最短路，这个没法保证的。以下引用一个别人的回答：
在一棵最小生成树中，两点的距离在整个图中是最短的吗？？？
不一定
比如5个点连了一圈边5个边中有四个长度1，一个长度2
那么最小生成树是选4个长度为1的边
但是长度为2的边连接的两个点之间最短路是2，没必要绕一圈。
因此，对于最短路问题还是要使用Dijkstra算法，或者Ford算法
在一棵最小生成树中，两点的距离在整个图中是最短的吗？？？
不一定
比如5个点连了一圈边5个边中有四个长度1，一个长度2
那么最小生成树是选4个长度为1的边
但是长度为2的边连接的两个点之间最短路是2，没必要绕一圈。
因此，对于最短路问题还是要使用Dijkstra算法，或者Ford算法
我要举报
如以上问答内容为低俗、色情、不良、暴力、侵权、涉及违法等信息，可以点下面链接进行举报！
大家都在看
推荐资讯