一个最小生成树为最短路树的判定算法

摘要

目的:给出一个最小生成树为最短路树的判定算法。方法:本文基于Dijkstra算法和Prim算法,首先利用Dijkstra算法计算给定源点0到任意节点i的最短路权重,然后利用改进的Prim算法构造最小生成树,在每次增加权重最小边时,考虑新增顶点到源点0的路径权重和恰好为从源点0到新增顶点的最短路权重,如果存在这样的最短路则继续构造,直到得到一个最小生成树恰好就是单源最短路生成树。结果:给出了一个最小生成树为最短路树的判定算法。结论:通过算法分析和算例验证了算法的可行性,在节点数较小时算法效率较好。