算法笔记 图论和优先级队列的笔记

图论

DFS       stack     O(h)     不具有最短性

BFS       queue    O(2^h)   最短路

迪杰斯特拉算法 Dijkstra算法

• 初始化：

  • 将起始节点 A 的距离设为 0。
  • 将其他所有节点的距离设为无穷大。
  • 创建一个优先队列，并将起始节点 A 加入优先队列。

• 处理队列：

  • 从优先队列中取出距离最小的节点 u。
  • 对于 u 的每个邻接节点 v，计算从 u 到 v 的路径长度，如果该长度小于当前记录的 v 的最短路径，则更新 v 的最短路径并将 v 加入优先队列。

  Floyd多元最短路  O(n^3)

  for(int k=1;k d2 时，e1 被认为优先级更高，排在 e2 前面。

• 因此，较小的 d 会被认为优先级较低。

  结论：

  这个比较函数实际上创建了一个 最小堆，因为 priority_queue 会根据 d 的值按升序排列，即优先处理 d 值较小的元素。