Dijkstra最短路径算法构造的生成树是否一定为最小生成树
问题描述:一连通无向图,边为非负权值,问用Dijkstra最短路径算法能否给出一棵生成树,这树是否一定为最小生成树?说明理由。
解答:Dijkstra最短路径算法能够给出一棵生成树,但该树不一定为最小生成树。虽然Dijkstra算法和Prim算法的思路与步骤较为相似,但两者的更新算法不一致,而其余部分完全一致。
Dijkstra算法对应的Min更新算法为:
if(Min[j] > Min[k] + G[k][j])
Min[j] = Min[k] + G[k][j];
而Prim算法对应的Min更新算法为:
if(Min[j] > G[k][j])
Min[j] = G[k][j]
为此,可考虑以下的反例:
对于以下的带权连通无向图
用Prim算法构造的一棵最小生成树为:
而用Dijkstra算法构造的一棵生成树为:
其中,Dijkstra算法的执行过程中,从v1到v3的最短路径选择的是v1->v3,而不是v1->v4->v3,原因是Min[3]=Min[4]+G[4][3],即v1到v3的初始最短距离与v1到v4的最短路径加上v4到v3的距离相等,因此在更新过程中保留v1->v3的最短路径为v1->v3而非v1->v4->v3,所以最后,构造的生成树的边权值之和为1+4+6=11,远大于用Prim算法构造的最小生成树边权值之和1+2+4=7。