Prim算法与Dijsktra算法的异同

写完最小生成树与最短路，大脑一片混乱。。。尤其是prim与dijsktra。。。理了一晚上才出来。。。

先回顾一下

Dijsktra：求单源最短路

Dijkstra() {
    for each u in G,V {
        //此处做初始化操作，给每个节点u赋键值+∞，设置空为父节点
        u.key = +∞
        u.parent = NULL
    }
    //选初始点r，Q是无向图G中所有点V的权值优先队列，key可看作源点到u的距离
    r.key = 0
    Q = G,V
    while(Q != ∅) ｛
          //取出Q中权值最小值的点u
          u = extractMin(Q)
          //取点u连接的所有节点(即无向图G的邻接表中的第u个链表)
          for each v ∈ G.Adj[u] {
              if (v ∈ Q) and (w(u, v) < key) {
                  //若该节点仍在Q中且权值w(w,v)小于其原始权值，则进行松弛操作！
                  v.parent = u
                  v.key = w(u, v) + u.key
              }
          }
      }
}

Prim：求最小生成树

//无向图G, 权值w, 起始点r
MST(G, w, r) {
    for each u in G,V {
        //此处做初始化操作，给每个节点u赋键值+∞，设置空为父节点
        u.key = +∞
        u.parent = NULL
    }
    //选初始点r，Q是无向图G中所有点V的权值优先队列，key可看作u到下一个节点v的距离
    r.key = 0
    Q = G,V
    while(Q != ∅) ｛
          //取出Q中权值最小值的点u
          u = extractMin(Q)
          //取点u连接的所有节点(即无向图G的邻接表中的第u个链表)
          for each v ∈ G.Adj[u] {
              if (v ∈ Q) and (w(u, v) < key) {
                  //若该节点仍在Q中且权值w(w,v)小于其原始权值，则进行松弛操作！
                  v.parent = u
                  v.key = w(u, v)
              }
          }
      }
}

异

【通过找不同，两个伪算法的差别只在于最后循环体内的松弛操作。

最小生成树只关心所有边的和最小，所以有v.key = w(u, v)，即每个点直连其他点的最小值（最多只有两个节点之间的权值和）

最短路径树只搜索权值最小，所以有v.key = w(u, v) + u.key，即每个点到其他点的最小值（最少是两个节之间的权值和）

简单总结就是，Dijkstra的松弛操作加上了到起点的距离，而Prim只有相邻节点的权值。

同

思想

都是使用贪心和线性规划，每一步都是选择权值/花费最小的边。
贪心：一个局部最有解也是全局最优解；
线性规划：主问题包含n个子问题，而且其中有重叠的子问题。

Dijkstra算法通过线性规划缓存了最优子路径的解，每一步也通过贪心算法来选择最小的边。
Prim算法通过贪心来选择最小的边，而Prim的每个子树都是最小生成树说明满足线性规划的两个条件。

时间复杂度

Time = θ( V * T1 + E * T2)
其中T1为取出键值最小点的时间，T2为降低键值的时间，取决于数据结构。

数组
T1= O(V), T2 = O(1), TIME = O(V * V + E) = O(V * V)
二叉堆
T1 = O(lgV), T2 = O(lgV), TIME = O(V * lgV + E * lgV)
斐波那契堆
T1 = O(lgV), T2 = O(1), TIME = O(V * lgV + E) = O(V * lgV)
对于稀疏图来说，E远小于V*V，所以二叉堆比较好；
而对于密集图来说，E=V*V，所以数组比较好；
斐波那契堆是最好的情况。