UOJ Logo gaomaoqi2022的博客

博客

P算法与Dij算法的区别

2020-04-02 20:51:26 By gaomaoqi2022

距离上,Prim是让整个集合看距离,而这个集合是一堆边

Dijkstra是从原点开始更新距离,然后点连点更新距离;

连点上,Prim是一个集合(边)连所有点

Dijkstra是一个点只能连直接与自己相关联的点,在开始连接新的点的时候,从最小的点开始继续访问

Dijkstra之所以选当前最小的点开始继续连点是因为最小的点可以有期望让到其他的点的边权尽量小

Prim算法数组里存的是点到集合的距离 Dijkstra算法数组里存的是所有点到总的原点1的距离

评论

happyguy
1

发表评论

可以用@mike来提到mike这个用户,mike会被高亮显示。如果你真的想打“@”这个字符,请用“@@”。