1. 朴素 dijkstra 算法: 稠密图-\(O(n^2)\)

1.1 具体步骤

1.1.0 定义:

• \(v_1\) 为源点, \(v_n\) 为终点
• 对于 \(set\) 集合中的点 \(v_i\), 其所对应的 \(d_i\) 表示从 \(v_1\) 到 \(v_i\) 的最短距离
• \(g_{src, dst}\) 表示从 \(src\) 点到 \(dst\) 点的距离

1.1.1 实现:

0. 设置 \(d_i = +\infty (i \in [1, n])\), 且 \(d_1 = 0\), \(set = \varnothing\)
1. 令 \(d_i = min(d_1, d_2, d_3, ..., d_n)\), 将 \(d_i\) 所对应的点\(v_i(v_i \not\in set)\) 所对应的点 \(v_i\) 加入到 \(set\) 集合中. 如果目标点 \(v_n\) 被加入到 \(set\) 集合, 则 dijkstra 算法结束, 否则继续第二步
2. 根据 \(v_i\) 扩展与 \(v_i\) 直接相连的所有点 \(v_k\) 到源点的距离 \(d_k = min(d_k, d_i + g_{i, k})\), 再继续第一步

1.2 代码

int dist[N]; // dist[i] 表示从源点到 i 点的距离
int g[N][N]; // g[i][j] 表示从 i 点到 j 点的距离
bool st[N]; // st[i] == true 表示 dist[i] 已经是源点到 i 点的最短距离了

int dijkstra() {
  memset(dist, 0x3f, sizeof(dist)); // 将所有点到源点的距离初始化为正无穷
  dist[1] = 0;
  
  for (int i = 0; i < n; ++ i) {
    // 选取所有不在 set 集合中的距离源点最近的点 t, 将其加入 set 集合
    int t = -1;
    for (int j = 1; j <= n; ++ j)
      if (!st[j] && (t == -1 || dist[t] > dist[j]))
        t = j;
        
    st[t] = true;
    // 如果终点已经在 set 集合中, 则 dijkstra 算法结束
    if (st[n]) break;
    
    // 尝试更新 t 点所连接的所有的点到源点的距离
    for (int j = 1; j <= n; ++ j)
      dist[j] = min(dist[j], dist[t] + g[t][j]);
  }
  
  return dist[n] == 0x3f3f3f3f ? -1 : dist[n];
}

1.3 证明

加入 \(set\) 集合的点 \(v_i\), 其所对应的 \(d_i\) 一定是其到源点的最小距离

1. 假设对于 \(v_i\), 其 \(d_i\) 不是最小的, 那么其一定会被另一个点 \(v_k\) 更新
2. 然而由于 \(v_k\) 在 \(v_i\) 之后被加入 \(set\) 集合, 而图中又没有负权边, 所以 \(d_k \geq d_i\), 故 \(d_k + g_{k, i} \geq d_i\), 即假设不成立, 正确性得证

2. 堆优化 dijkstra 算法: 稀疏图-\(O(mlogn)\)

2.1 代码

int dijkstra() {
  memset(dist, 0x3f, sizeof(dist));
  priority_queue<PII, vector<PII>, greater<PII>> q; // 小根堆
  q.push({dist[1] = 0, 1}); // first 为距离 d, second 为点 v
  
  while (!q.empty()) {
    auto t = q.top(); // 取出到源点距离最小的点
    q.pop();
    
    int dis = t.first;
    int v = t.second;
    
    if (st[v]) continue;
    st[v] = true; // 加入到 set 集合
    
    // h[v] 表示 v 点所能到的所有点的链表集合的 head
    // e[i] 表示 v 点所能直接到的点
    // w[i] 表示 v 点到 e[i] 点的距离
    // ne[i] 指向下一个节点
    for (int i = h[v]; ~i; i = ne[i])
      if (dist[e[i]] > dis + w[i]) {
        dist[e[i]] = dis + w[i];
        q.push({dist[e[i]], e[i]});
      }
  }
  
  return dist[n] == 0x3f3f3f3f ? -1 : dist[n];
}