面试题：C++ 中处理负权边的 Dijkstra 算法变体

设计思路

分层图思想：
- 对于常规Dijkstra算法，其贪心策略基于边权非负。为处理负权边，我们引入分层图的概念。
- 假设图有n个节点，我们构建k层图，每层图都包含原始图的所有节点。
- 从一层图到下一层图的转换通过经过负权边实现。具体来说，当从某层的节点u通过负权边(u, v, w)到节点v时，我们会进入下一层图中的节点v。这样，我们把处理负权边的过程转化为在不同层图之间的移动。
修改距离更新规则：
- 在常规Dijkstra算法中，只根据边权更新距离。在新算法中，由于存在层的概念，我们不仅要考虑边权，还要考虑层的变化对距离的影响。当从一层移动到下一层时，我们需要调整距离计算方式，以反映负权边的影响。

数据结构选择

邻接表：
- 用于存储图的结构。对于每个节点，邻接表存储与该节点相连的边及其权值。这是一种常见且高效的图存储方式，空间复杂度为$O(V + E)$，其中V是节点数，E是边数。
- 示例代码：
```
struct Edge {
    int to;
    int weight;
    Edge(int t, int w) : to(t), weight(w) {}
};
vector<vector<Edge>> graph;
```
优先队列：
- 用于实现Dijkstra算法中的优先队列，存储节点及其当前的最小距离。优先队列按照距离从小到大排序，每次取出距离最小的节点进行扩展。
- 在C++中，可以使用std::priority_queue，并自定义比较函数来按照距离排序。
- 示例代码：
```
struct Compare {
    bool operator()(const pair<int, int>& a, const pair<int, int>& b) {
        return a.second > b.second;
    }
};
priority_queue<pair<int, int>, vector<pair<int, int>>, Compare> pq;
```
二维数组：
- 用于记录每个节点在不同层的最小距离。例如，dist[i][j]表示在第j层图中节点i的最小距离。
- 示例代码：
```
vector<vector<int>> dist;
```

算法流程

初始化：
- 初始化图的邻接表，将所有边加入邻接表中。
- 初始化距离数组dist，将所有dist[i][j]设为无穷大，dist[start][0]设为0，其中start是起始节点。
- 将起始节点(start, 0, 0)（节点编号，层编号，距离）加入优先队列pq。
循环扩展：
- 从优先队列pq中取出距离最小的节点(node, layer, curDist)。
- 如果当前节点(node, layer)的距离curDist大于dist[node][layer]，说明该节点已经被更优解处理过，跳过。
- 遍历当前节点node的所有邻接边(node, neighbor, weight)：
  - 如果weight >= 0：
    - 计算新距离newDist = curDist + weight。
    - 如果newDist < dist[neighbor][layer]，更新dist[neighbor][layer] = newDist，并将(neighbor, layer, newDist)加入优先队列pq。
  - 如果weight < 0：
    - 计算新距离newDist = curDist + weight。
    - 计算新层newLayer = layer + 1。
    - 如果newDist < dist[neighbor][newLayer]，更新dist[neighbor][newLayer] = newDist，并将(neighbor, newLayer, newDist)加入优先队列pq。
结果获取：
- 最终，在所有层中找到目标节点的最小距离，即为从起始节点到目标节点的最小距离。

代码实现

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

using namespace std;

struct Edge {
    int to;
    int weight;
    Edge(int t, int w) : to(t), weight(w) {}
};

struct Compare {
    bool operator()(const pair<int, int>& a, const pair<int, int>& b) {
        return a.second > b.second;
    }
};

int modifiedDijkstra(int start, int end, int numNodes, int numLayers, vector<vector<Edge>>& graph) {
    vector<vector<int>> dist(numNodes, vector<int>(numLayers, numeric_limits<int>::max()));
    dist[start][0] = 0;
    priority_queue<pair<int, int>, vector<pair<int, int>>, Compare> pq;
    pq.push({start, 0});

    while (!pq.empty()) {
        auto [node, curDist] = pq.top();
        int layer = 0;
        for (int i = 0; i < numLayers; ++i) {
            if (dist[node][i] == curDist) {
                layer = i;
                break;
            }
        }
        pq.pop();

        if (curDist > dist[node][layer]) continue;

        for (const auto& edge : graph[node]) {
            int neighbor = edge.to;
            int weight = edge.weight;
            if (weight >= 0) {
                int newDist = curDist + weight;
                if (newDist < dist[neighbor][layer]) {
                    dist[neighbor][layer] = newDist;
                    pq.push({neighbor, newDist});
                }
            } else {
                int newDist = curDist + weight;
                int newLayer = layer + 1;
                if (newLayer < numLayers && newDist < dist[neighbor][newLayer]) {
                    dist[neighbor][newLayer] = newDist;
                    pq.push({neighbor, newDist});
                }
            }
        }
    }

    int minDist = numeric_limits<int>::max();
    for (int i = 0; i < numLayers; ++i) {
        minDist = min(minDist, dist[end][i]);
    }
    return minDist;
}

时间复杂度分析

优先队列操作：
- 每次从优先队列中取出节点的时间复杂度为$O(\log (V \times k))$，其中V是节点数，k是层数。
- 每个节点最多被加入优先队列k次（因为有k层），总共有V个节点，所以优先队列操作的总时间复杂度为$O((V \times k)\log (V \times k))$。
邻接表遍历：
- 对于每条边，我们最多进行一次扩展操作，时间复杂度为$O(E)$，其中E是边数。
- 综合起来，新算法的时间复杂度为$O((V \times k)\log (V \times k)+E)$。

空间复杂度分析

邻接表：
- 邻接表存储图的空间复杂度为$O(V + E)$。
优先队列：
- 优先队列中最多存储$V \times k$个元素，空间复杂度为$O(V \times k)$。
距离数组：
- 距离数组dist的空间复杂度为$O(V \times k)$。
- 综合起来，新算法的空间复杂度为$O(V + E+V \times k)$。

星途面试题库

面试题：C++ 中处理负权边的 Dijkstra 算法变体

知识考点

面试题答案

设计思路

数据结构选择

算法流程

代码实现

时间复杂度分析

空间复杂度分析