最短路径

一、Dijkstra（单源最短路）

1.Dijkstra算法简介

迪杰斯特拉算法（Dijkstra’s Algorithm）是一种经典的最短路径算法，用于寻找加权图中从源点到其他各个顶点的最短路径。该算法常用于单源最短路径问题，即已知图中一个起点（源点），计算它到其他所有顶点的最短路径，前提是权重是非负的。

2. 算法思想

迪杰斯特拉算法通过逐步扩展最短路径来构建最终的最短路径树，其基本思想如下：

• 从起点出发，逐步找到离起点最近的顶点，并计算路径长度。
• 每次选出当前未访问过的最短路径的顶点，更新起点到其他顶点的最短距离。
• 直到所有顶点都被访问，算法结束。

3. 算法步骤

1. 初始化：设定源点到自身的距离为0，其他顶点到源点的距离为∞（表示不可达）。
2. 选取未访问的顶点中距离源点最近的顶点作为当前顶点，记为 u，标记其为已访问。
3. 遍历从顶点 u 出发的所有边，更新从源点到邻接点的距离。如果从源点通过 u 到达邻接点的距离更短，则更新邻接点的距离。
4. 重复步骤2和步骤3，直到所有顶点都被访问。
5. 最终结果是源点到每个顶点的最短路径。

4. 代码实现（主要部分）

// 迪杰斯特拉算法函数
vector<int> dijkstra(int start, int n, const vector<vector<int>>& graph) {
    // 初始化距离数组，设为无穷大
    vector<int> dist(n, INT_MAX);
    // 标记数组，记录是否访问过
    vector<bool> visited(n, false);

    // 起点距离设为0
    dist[start] = 0;

    // 主循环：对每个顶点找到最短路径
    for (int i = 0; i < n; ++i) {
        // 找到未访问的顶点中距离最小的顶点
        int u = -1;
        int minDist = INT_MAX;
        for (int j = 0; j < n; ++j) {
            if (!visited[j] && dist[j] < minDist) {
                u = j;
                minDist = dist[j];
            }
        }

        // 如果找不到这样的顶点，说明剩余顶点不可达，退出循环
        if (u == -1) break;

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

        // 更新从当前顶点出发到其他顶点的最短距离
        for (int v = 0; v < n; ++v) {
            if (graph[u][v] != 0 && !visited[v]) { // 如果有边并且未访问
                dist[v] = min(dist[v], dist[u] + graph[u][v]);
            }
        }
    }

    return dist;
}

二、Floyd（多源最短路）

1.Floyd算法简介

Floyd算法（弗洛伊德算法）是一种用于求解加权图中任意两点最短路径的经典算法。与Dijkstra算法和Bellman-Ford算法不同的是，Floyd算法不只是计算单点到其他点的最短路径，而是能够计算出所有点之间的最短路径，因此常用于多源最短路径问题。

2.算法思想

Floyd算法的核心思想是使用动态规划的方式，不断尝试在两点之间插入中间节点，并更新最短路径。具体而言，假设图中有 (n) 个顶点，Floyd算法使用三重循环逐步检查是否能通过某个中间顶点 (k) 使两个顶点 (i) 和 (j) 的距离更短。

3.算法步骤

设dist[i][j] 表示节点 (i) 到节点 (j) 的最短距离。

算法流程如下：

1. 初始化距离矩阵 dist。若顶点 (i) 到 (j) 有直接边权，则 dist[i][j] 设为该边权；否则设为一个较大的值（如 INF）。
2. 依次遍历每个节点 (k)，对于每对节点 (i) 和 (j)，尝试通过节点 (k) 更新 dist[i][j] = min(dist[i][k] + dist[k][j])
3. 经过上述操作，dist[i][j] 会记录 (i) 到 (j) 的最短路径。

4.代码实现（主要部分）

const int INF = 1e9; // 表示无穷大的数值

// Floyd算法计算任意两点之间的最短路径
void floydWarshall(vector<vector<int>>& dist, int n) {
    for (int k = 0; k < n; ++k) {
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < n; ++j) {
                if (dist[i][k] != INF && dist[k][j] != INF) { 
                    dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
                }
            }
        }
    }
}

int main() {
    // 初始化距离矩阵
    vector<vector<int>> dist(n, vector<int>(n, INF));

    // 节点到自身的距离为0
    for (int i = 0; i < n; ++i)
        dist[i][i] = 0;

    for (int i = 0; i < m; ++i) { // 初始化
        int u, v, w;
        cin >> u >> v >> w;
        dist[u][v] = w; // 无向图的话再加一句 dist[v][u] = w;
    }

    // 执行Floyd算法
    floydWarshall(dist, n);
    return 0;
}

三、SPFA（含有负边权单源最短路）

1.SPFA算法简介

SPFA（Shortest Path Faster Algorithm）是Bellman-Ford算法的队列优化版本，用于求解单源最短路径问题。该算法适用于含负权边（前提是不含负权回路）的图，并能检测图中是否存在负权环。其平均时间复杂度为 O(E)O(E)，最坏情况下为 O(VE)O(V**E)，在稀疏图中表现优异。

2.算法思想

• 利用队列维护待更新的顶点集合，只对队列中的节点进行松弛操作，从而减少不必要的重复更新。

• 每当从队列中取出一个顶点 u 后，遍历其所有出边，如果能通过 u 更新原点到 u的邻接点 v 的距离，则将 v 放入队列（如果它还不在队列中）。

3.算法步骤

1. 初始化：设置源点到自身的距离为0，其他顶点为无穷大（INF）。将源点加入队列，并标记为“在队列中”。
2. 取出队首顶点：取出队列头部顶点 u，标记为“不在队列中”。
3. 遍历邻接边：对 u 的所有邻接边 u→v 进行松弛操作：若 dist[v] > dist[u] + weight(u, v)，则更新 dist[v]。
4. 入队条件：若 v 的距离被更新且当前不在队列中，则将 v 加入队列尾部，并标记为“在队列中”。
5. 循环终止条件：重复上述过程直到队列为空。
6. 负权环检测：若某个顶点入队次数超过顶点总数 n，说明图中存在负权环。

4.代码实现（主要部分）

const int INF = 1e9; // 表示无穷大

vector<int> spfa(int start, int n, const vector<vector<pair<int, int>>>& graph) {
    vector<int> dist(n, INF);       // 存储最短距离
    vector<int> cnt(n, 0);          // 记录顶点入队次数（用于检测负环）
    vector<bool> inQueue(n, false); // 标记顶点是否在队列中
    queue<int> q;                   // 队列用于存储待处理的顶点

    // 初始化源点
    dist[start] = 0;
    q.push(start);
    inQueue[start] = true;
    cnt[start]++;

    // 主循环处理队列中的顶点
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        inQueue[u] = false; // 标记为不在队列中

        // 遍历所有邻接边
        for (auto& edge : graph[u]) {
            int v = edge.first;  // 邻接顶点
            int w = edge.second; // 边的权重

            // 尝试松弛操作
            if (dist[v] > dist[u] + w) {
                dist[v] = dist[u] + w;

                // 若顶点v不在队列中，则加入队列
                if (!inQueue[v]) {
                    q.push(v);
                    inQueue[v] = true;
                    cnt[v]++;

                    // 检测负权环：入队次数超过n次则存在负环
                    if (cnt[v] > n) {
                        // 返回空数组表示检测到负环，或抛出异常
                        return vector<int>();
                    }
                }
            }
        }
    }

    return dist;
}