面试题：C++ 优化 Dijkstra 算法的实现

1. 优化后的 Dijkstra 算法 C++ 实现

#include <iostream>
#include <vector>
#include <queue>
#include <limits>

using namespace std;

const int INF = numeric_limits<int>::max();

// 边的结构体
struct Edge {
    int to;
    int weight;
    Edge(int t, int w) : to(t), weight(w) {}
};

// 优化后的 Dijkstra 算法
void optimizedDijkstra(vector<vector<Edge>>& graph, int start) {
    int n = graph.size();
    vector<int> dist(n, INF);
    vector<bool> visited(n, false);
    dist[start] = 0;

    // 使用优先队列，按照距离从小到大排序
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
    pq.push({0, start});

    while (!pq.empty()) {
        int u = pq.top().second;
        pq.pop();

        if (visited[u]) continue;
        visited[u] = true;

        for (const Edge& edge : graph[u]) {
            int v = edge.to;
            int weight = edge.weight;
            if (!visited[v] && dist[u] + weight < dist[v]) {
                dist[v] = dist[u] + weight;
                pq.push({dist[v], v});
            }
        }
    }

    // 输出结果
    for (int i = 0; i < n; ++i) {
        cout << "Distance from " << start << " to " << i << " is: " << dist[i] << endl;
    }
}

2. 时间复杂度提升原理

常规 Dijkstra 算法：每次寻找距离源点最近的未访问顶点时，需要遍历所有顶点，时间复杂度为 $O(V^2)$，其中 $V$ 是顶点的数量。
优化后的 Dijkstra 算法：使用优先队列（最小堆）来存储顶点及其距离，每次从优先队列中取出距离最小的顶点，这个操作的时间复杂度为 $O(\log V)$。而对于每个顶点的每条边，将其邻接顶点及其距离加入优先队列的操作时间复杂度也是 $O(\log V)$。因此，总的时间复杂度变为 $O((V + E)\log V)$，其中 $E$ 是边的数量。当图是稀疏图（$E << V^2$）时，优化后的算法时间复杂度有显著提升。

3. 代码关键步骤作用

Edge 结构体：定义边的信息，包括目标顶点 to 和权重 weight。
optimizedDijkstra 函数：实现优化后的 Dijkstra 算法。
- 初始化部分：
  - vector<int> dist(n, INF)：初始化距离数组，将所有顶点到源点的距离设为无穷大。
  - vector<bool> visited(n, false)：初始化访问数组，标记所有顶点未被访问。
  - dist[start] = 0：将源点到自身的距离设为 0。
- 优先队列部分：
  - priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq：定义一个优先队列，按照距离从小到大排序，存储顶点及其到源点的距离。
  - pq.push({0, start})：将源点及其距离（0）加入优先队列。
- 主循环部分：
  - int u = pq.top().second 和 pq.pop()：从优先队列中取出距离最小的顶点。
  - if (visited[u]) continue：如果该顶点已被访问过，则跳过，防止重复计算。
  - 内层 for 循环：遍历当前顶点 u 的所有邻接顶点 v，如果 v 未被访问且通过 u 到 v 的距离比当前记录的 v 到源点的距离更小，则更新 v 的距离，并将 v 及其新距离加入优先队列。
- 输出部分：遍历距离数组，输出源点到各个顶点的最短距离。

面试题：C++ 优化 Dijkstra 算法的实现

知识考点

面试题答案

1. 优化后的 Dijkstra 算法 C++ 实现

2. 时间复杂度提升原理

3. 代码关键步骤作用