使用优先队列的 C++ Dijkstra 算法

在本文中，我们将看到使用 C++ STL 优先队列实现的 Dijkstra 算法。Dijkstra 算法用于在无向图中找到从源到目的地的最短路径。

一个有边的权重的图如下所示

让我们考虑一个源顶点 0，我们必须找到从源顶点到图中所有顶点的最短路径。

源顶点 = 0

创建图结构

我们将创建一个 Graph 类，其数据成员为

• int v - 存储图中顶点的数量
• 对列表 - 存储顶点和与特定顶点关联的权重。

list> *adj;

构造函数

我们需要一个构造函数来分配邻接表的内存。

如何向图中添加一条边？

创建的对列表有两个参数。一个包含顶点，另一个包含与其关联的权重。

由于图是双向的，我们可以将相同的权重添加到相反的顶点。

编码

算法

1. 将距源的初始距离标记为无限。
2. 创建一个空的优先队列 PQ。PQ 的每个项都是一个对（权重，顶点）。权重（或距离）用作对的第一个项，因为第一个项默认用于比较两个对。
3. 将源顶点插入 PQ，并将其距离设为 0。
4. 直到定义的优先队列 PQ 变空。执行操作 a 和 b。
   1. 从 PQ 中提取最小距离顶点，并设为 u。
   2. 遍历 u 的所有邻居并执行
      对每个顶点 v 执行以下操作。
      // 如果存在到 v 的更短路径
      // 经过 u。
      如果 dist[v] > dist[u] + weight(u, v) // (v) 的距离 > (u) 的距离和从 u 到 v 的权重
      1. 更新 v 的距离，即执行
         dist[v] = dist[u] + weight(u, v)
      2. 将 v 插入 PQ（即使 v 已经
         存在）
5. 遍历 dist[] 数组以打印从源到所有顶点的最短路径。

C++ 代码

输出

Vertex   Distance from Source
0 		   0
1 		   4
2 		  12
3 		  19
4 		  21
5 		  11
6 		   9
7 	           8
8 		  14