Dijkstra算法与Prim算法的异同

Dijkstra简述

Dijkstra算法用于构建单源点的最短路径树(MST)——即树中某个点到任何其他点的距离都是最短的。例如，构建地图应用时查找自己的坐标离某个地标的最短距离。可以用于有向图，但是不能存在负权值(Bellman-Ford可以处理负权值)。

伪代码

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简述

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)
}
}
}
}


###异
MST中任意AB两点之间的距离，并不比原始图中AB的距离短，即原始图中可能存在边E(A,B)**小于**MST中的E(A,B)。
注意上述两个伪算法的差别只在于最后循环体内的**松弛操作**。
- 最小生成树只关心所有边的和最小，所以有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，所以数组比较好；
**斐波那契堆**是最好的情况。

####Dijkstra特例
当边的权值都为1的时候，可以用DFS（广度优先搜索）优化时间复杂度。
- 使用FIFO（先进先出）队列代替优先队列，优化了降低键值T2的操作为O(1)
- 松弛操作改为

if d[v] = +∞ {
    d[v] = d[u] + 1
    enqueue(Q, v)
}

优化了取出键值最小点的时间T1 = O(1)

总的时间复杂度TIME = V + E

Dijkstra算法与Prim算法的异同