Dijkstra算法与Prim算法区别

Dijkstra算法和Prim算法都是图论中用于寻找最小生成树（Minimum Spanning Tree, MST）的两种经典算法，它们在应用场景和搜索策略上有所不同。

1. Dijkstra算法：
- **目标**：寻找从一个给定源节点到图中所有其他节点的最短路径。
- **策略**：按贪心策略进行，每次选择当前未访问节点中距离源节点最近的一个进行扩展，更新其邻居节点的距离。
- **适用场景**：适用于非负权值的边，如求最短路径问题。
- **数据结构**：使用优先队列（通常为斐波那契堆）来保持未探索节点的有序集合。

2. Prim算法：
- **目标**：构建一个连接所有顶点的最小生成树。
- **策略**：开始时从任意一个顶点开始，然后逐步添加与生成树相连的最小权重边，每次选择与当前生成树相连且未加入的最小边。
- **适用场景**：同样适用于非负权值图，但可以处理边集中的负权重，但须满足一定条件（例如每条边恰好被加入一次）。
- **数据结构**：通常使用一个已加入最小生成树的集合和剩余边的集合（通常是邻接表）来进行操作。