Dijkstra 与 Prim 算法的区别
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
版权声明:文章版权归本人所有,欢迎转载,但必须保留此段声明,且在文章页面明显位置给出原文链接,否则保留追究法律责任的权利。