Dijkstra 算法与 Prim 算法非常相似,甚至很多初学者觉得它们就是一样的。它们最直观的区别就是目的不同:前者求解最短路径,后者求解最小生成树。

对比上图,

  • 最短路径

    a->b  @length = 2
    a->c  @length = 3
  • 最小生成树

    a->b->c  @sum = 4

结论:两者不一样!

好,最后让我们回归代码。

Dijkstra 算法与 Prim 算法都有一个数组,不妨统一称为 R[],我们每次都是取 R[] 的最小值,接着更新 R[],再取其最小值,,,往复下去。而这两者的区别就发生在更新操作之中。

  • 最短路径

    for the weight of edge(u->v)
        if R[v] > R[u] + weight
            R[v] = R[u] + weight
  • 最小生成树

    for the weight of edge(u->v)
        if R[v] > weight
            R[v] = weight

其区别,从代码来看,显而易见。

其它

文章开源在 Github - blog-articles,点击 Watch 即可订阅本博客。 若文章有错误,请在 Issues 中提出,我会及时回复,谢谢。

如果您觉得文章不错,或者在生活和工作中帮助到了您,不妨给个 Star,谢谢。

(文章完)

文章作者:刘毅 (Ethson Liu)
发布日期:2019-11-23
原文链接:https://ethsonliu.com/2019/11/the-difference-of-dijkstra-and-prim-algorithm.html
版权声明:文章版权归本人所有,欢迎转载,但必须保留此段声明,且在文章页面明显位置给出原文链接,否则保留追究法律责任的权利。