【两个算法的回顾】

    Prim Dijkstra
    用途 树中所有边的权值之和最小 某个点到任何其他点的距离都是最短的
    思想 ①以顶点为操作对象，每次选择一个顶点并入子图；
    ②顶点的选择依据：子图顶点到其他顶点的最短边    		 ①以顶点为操作对象，每次选择一个顶点并入子图；
    ②顶点选择依据：起点到其他顶点的最短路径
    数据结构 ①子图vest[i]：结点i是否已并入生成树；
    ②lowcost[i]：结点i到子树的最短边权重    		 ①子图set[i]：结点i是否在子图中
    ②dist[i]：起点v0到结点i的最短路径值为dist[i]
    ③path[i]：为该路径中i的前一个结点
    代码 Prim与Dijkstra的异同 - 图1 Prim与Dijkstra的异同 - 图2

    【两者的异同】

    Prim Dijkstra 两者相同之处
    适用性 无向连通图 无向图、有向图（不能处理负权值）
    用途 树中所有边的权值之和最小 某个点到任何其他点的距离都是最短的
    松弛操作 考虑的是相邻结点的权值（每次选择是最小边）
    即每个点直连其他点的最小值（无中转点）    		 考虑起点到其他点的权值（每次选择的是最短路径）
    即每个点到其他点的最小值（有中转点）    		 两者的每一步都是选择最小
    更新操作 Prim与Dijkstra的异同 - 图3 Prim与Dijkstra的异同 - 图4
    生成的结果 图的最小生成树 构建单源点的最短路径树 都是生成树，结果可能相同
    思想 通过贪婪来选择最小的边，而Prim的每个子树都是最小生成树说明满足线性规划的两个条件 通过线性规划缓存了最优子路径的解，每一步也通过贪婪算法来选择最小的边 两者都使用贪婪和线性规划
    例子对比 为N个村庄修路，花销最小 单个村庄到其他村庄的最短路径

    【相关解释】

    • 【贪婪】一个局部最优解也是全局最优解
    • 【线性规划】主问题包含了n个子问题，而且其中有重叠的子问题

    【参考文章】