运筹学最短路问题一般使用的方法是Dijkstra标号法,现在想请问能否用另外一种办法,即先画出最小支撑树,然后再进行计算,能否严格证明一下?急用,

Question

运筹学最短路问题
一般使用的方法是Dijkstra标号法,现在想请问能否用另外一种办法,即先画出最小支撑树,然后再进行计算,能否严格证明一下?急用,

Answer 1

通过最小支撑树来求最短路的想法是不是认为求得了一个图的最小支撑树,则最小支撑树上任意两点间的链就是要求的最短路,这个没法保证的.以下引用一个别人的回答：
在一棵最小生成树中,两点的距离在整个图中是最短的吗?
不一定
比如5个点连了一圈边 5个边中有四个长度1,一个长度2
那么最小生成树是选4个长度为1的边
但是长度为2的边连接的两个点之间最短路是2,没必要绕一圈.
因此,对于最短路问题还是要使用Dijkstra算法,或者Ford算法