Dijkstra算法与Prim算法的异同

作者: 豆沙包67 | 来源:发表于2016-06-04 10:42 被阅读612次

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算法的异同

    Dijkstra简述 Dijkstra算法用于构建单源点的最短路径树(MST)——即树中某个点到任何其他点的距离都...

  • 最短路算法

    与最小生成树有些不一样.在这里提出三种算法.dijkstra算法,是最普通也是最简单的.与prim算法有些类似,但...

  • 图的结构 BFS DFS

    题目:BFS 一个队列,一个set集合 题目:DFS 题目:Kruskal算法 题目:Prim Dijkstra算法

  • JavaScript模拟图操作

    JS操作实现无向网的Prim算法 最后输出结果如下: 其中例子中的图如下: JavaScript实现Dijkstra算法

  • 算法学习(3)-最小生成树算法

    最小生成树Prim算法理解最小生成树-Prim算法和Kruskal算法Prim算法和Kruskal算法

  • 贪心算法--最小生成树Prim算法

    引言:前两天在复习贪心算法时,看到单源最短路径的Dijkstra算法和最小生成树的Prim算法,由于自己不认真,竟...

  • 考研--图论

    1、朴素Dijkstra算法 2、spfa 3、floyd 4、prim最小生成树稠密图, 5、Kruskal最小...

  • 图的最短路径

    Dijkstra算法&Floyd算法 一、Dijkstra算法 Dijkstra算法思想: 只计算v0出发到其他顶...

  • 图之最短路径算法--Dijkstra

    Dijkstra算法作者获得过图灵奖,非常著名。该算法能求出给定点到图中所有其它顶点的最短路径。其道理和prim算...

  • Prim算法 Python实现代码

    本文只对Prim算法进行实现,若需了解算法原理可参考文末链接。 Prim算法原理

网友评论

    本文标题:Dijkstra算法与Prim算法的异同

    本文链接:https://www.haomeiwen.com/subject/sbghdttx.html