最短路解决 Dijkstra

用途

该算法可以算出从一个顶点到其余各顶点的最短路径，解决的是非负权图中最短路径问题

该算法的复杂度为 O(n)

核心思想

设定一些记号：

• n 为图上点的数目，m 为图上边的数目
• s 为最短路的源点
• D(u)为 s 点到 u 点的实际长度
• dis(u)为 s 点到 u 点的估计最短路长度 任何时候都有 dis(u) >= D(u) 当最短路算法终止时，应该有 dis(u) = D(u)
• w(u,v)为(u,v)这一条边的边权

将节点分为两个集合：已确定最短路径的点集(记作 S 集合)和未确定最短路长度的点集(记作 T 集合)

一开始所有的点都属于 T 集合 初始化 dis[s] = 0，其余点的 dis 均为 INF

然后重复操作：

1. 从 T 集合中，选取一个最短路长度最小的结点，移动到 S 集合中
2. 对那些刚刚被加入 S 集合的结点的所有出边执行松弛操作

直到 T 集合为空，算法结束

实现

暴力实现

时间复杂度 O(n²)

// 定义边的结构体
struct edge {
  int v, w;  // 目标顶点v，边的权重w
};

vector<edge> e[maxn];  // 邻接表，用于存储每个顶点的边
int dis[maxn];         // 存储从起点到每个顶点的最短距离
int vis[maxn];         // 标记顶点是否已被访问

void dijkstra(int n, int s) {
  // 将dis数组初始化为一个很大的值0x3f3f3f3f，表示所有顶点初始时的距离为无穷大
  memset(dis, 0x3f, (n + 1) * sizeof(int));
  dis[s] = 0;  // 起点s到自身的距离为0

  // 遍历所有顶点
  for (int i = 1; i <= n; i++) {
    int u = 0, mind = 0x3f3f3f3f;  // 初始化当前顶点u和最小距离mind

    // 查找未访问且距离最小的顶点 注意未访问这一点很关键 确保不会遗漏
    for (int j = 1; j <= n; j++)
      if (!vis[j] && dis[j] < mind) {
        u = j;
        mind = dis[j];
      }

    vis[u] = true;  // 标记顶点u为已访问

    // 遍历顶点u的所有邻接边
    for (auto ed : e[u]) {
      int v = ed.v, w = ed.w;  // 获取邻接顶点v和边的权重w

      // 如果通过顶点u到顶点v的路径更短，则更新dis[v]
      if (dis[v] > dis[u] + w) {
        dis[v] = dis[u] + w;
      }
    }
  }
}

优先队列实现

时间复杂度 O(mlogm)

// 定义节点结构体
struct node {
  int dis, u; // dis 是从源点到该节点的距离，u 是节点编号

  // 重载比较运算符，用于优先队列对节点进行排序
  bool operator>(const node& a) const { return dis > a.dis; }
};

vector<edge> e[maxn]; // 邻接表 e，存储图的边
int dis[maxn], vis[maxn]; // dis: 存储从源点到每个节点的最短距离; vis: 标记节点是否已访问
priority_queue<node, vector<node>, greater<node>> q; // 优先队列，节点按距离升序排列

// Dijkstra 算法函数，计算从源点 s 到其他节点的最短路径
void dijkstra(int n, int s) {
  memset(dis, 0x3f, (n + 1) * sizeof(int)); // 初始化 dis 数组，设为无穷大（0x3f3f3f3f）
  dis[s] = 0; // 源点到自身的距离为 0
  q.push({0, s}); // 将源点推入优先队列

  while (!q.empty()) { // 当优先队列不为空时
    int u = q.top().u; // 取出堆顶元素的节点编号
    q.pop(); // 弹出堆顶元素
    if (vis[u]) continue; // 如果该节点已被访问过，跳过
    vis[u] = 1; // 标记该节点已被访问

    for (auto ed : e[u]) { // 遍历与节点 u 相邻的所有边
      int v = ed.v, w = ed.w; // 获取边的终点和权重
      if (dis[v] > dis[u] + w) { // 如果从源点到 v 的距离大于从源点通过 u 到 v 的距离
        dis[v] = dis[u] + w; // 更新最短距离
        q.push({dis[v], v}); // 将更新后的节点推入优先队列
      }
    }
  }
}