Prim | Dijkstra | |
目的 | 最小生成树 | 单源最短路 |
让所有边权值之和最小 | 让每个顶点到源点路径上的权值最小 | |
贪心,不断更新每个顶点到整棵树的距离 | 贪心,不断更新每个顶点到源点的距离 | |
复杂度 | O(n^2),可堆优化到O(nlogn) | O(n^2),可堆优化到O(nlogn) |
当图无权时,求最短路,dijkstra算法 可用bfs代替
Prim | Dijkstra | |
目的 | 最小生成树 | 单源最短路 |
让所有边权值之和最小 | 让每个顶点到源点路径上的权值最小 | |
贪心,不断更新每个顶点到整棵树的距离 | 贪心,不断更新每个顶点到源点的距离 | |
复杂度 | O(n^2),可堆优化到O(nlogn) | O(n^2),可堆优化到O(nlogn) |
转:https://www.cnblogs.com/MicZ/archive/2012/10/01/2785366.html