最短路径算法

在图论中，最短路径问题是一类非常经典且实用的问题。本节将详细介绍几种常用的最短路径算法。

问题定义

【定义】给定一个图G=(V,E)，其中V是顶点集合，E是边集合，每条边有一个权值（距离或成本）。最短路径问题就是要找到从起点s到终点t之间的一条路径，使得路径上所有边的权值之和最小。

最短路径问题分为几种类型：

1. 单源最短路径：从一个源点到其他所有点的最短路径
2. 多源最短路径：任意两点之间的最短路径
3. 带负权边的最短路径
4. 带负权环的图中的最短路径问题（可能无解）

Dijkstra算法

【算法】Dijkstra算法是解决单源最短路径问题的经典算法，适用于所有边权为非负数的情况。

算法思想

1. 维护一个距离数组dist，dist[i]表示从源点s到顶点i的当前最短距离
2. 每次从未处理的顶点中选择距离最小的顶点u
3. 更新u的所有邻居v的距离：如果dist[u] + weight(u,v) < dist[v]，则更新dist[v]
4. 重复步骤2-3直到所有顶点都被处理

代码实现

基于优先队列的Dijkstra算法实现：

const int MAXN = 100005;
const int INF = 0x3f3f3f3f;

struct Edge {
    int to, weight;
    Edge(int _to, int _weight) : to(_to), weight(_weight) {}
};

vector<Edge> graph[MAXN];  // 邻接表表示的图
int dist[MAXN];            // 存储从源点到各点的最短距离
bool visited[MAXN];        // 标记顶点是否已经处理过

void dijkstra(int start, int n) {
    // 初始化
    for (int i = 1; i <= n; i++) {
        dist[i] = INF;
        visited[i] = false;
    }
    dist[start] = 0;

    // 使用优先队列优化，pair的first是距离，second是顶点编号
    // 小顶堆，距离小的优先出队
    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;

        // 更新u的所有邻居
        for (const Edge& e : graph[u]) {
            int v = e.to;
            int weight = e.weight;

            if (dist[u] + weight < dist[v]) {
                dist[v] = dist[u] + weight;
                pq.push({dist[v], v});
            }
        }
    }
}

时间复杂度分析

• 使用邻接矩阵：O(V²)
• 使用优先队列优化的邻接表：O((V+E)log V)

应用场景

1. 路径规划
2. 网络路由算法
3. 任何需要找到最小代价路径的问题

Bellman-Ford算法

【算法】Bellman-Ford算法也用于解决单源最短路径问题，但其可以处理带有负权边的图，还能检测负权环。

算法思想

1. 初始化dist[source]=0，其他dist[v]=∞
2. 对所有边进行V-1次松弛操作（因为最短路径最多包含V-1条边）
3. 再对所有边进行一次松弛操作，如果还有更新，说明存在负权环

代码实现

struct Edge {
    int from, to, weight;
};

vector<Edge> edges;  // 存储所有边
int dist[MAXN];      // 存储从源点到各点的最短距离

// 返回true表示没有负环，false表示存在负环
bool bellmanFord(int start, int n, int m) {
    // 初始化
    for (int i = 1; i <= n; i++) {
        dist[i] = INF;
    }
    dist[start] = 0;

    // 进行n-1次松弛
    for (int i = 1; i <= n - 1; i++) {
        bool updated = false;

        // 对每条边进行松弛操作
        for (const Edge& e : edges) {
            if (dist[e.from] != INF && dist[e.from] + e.weight < dist[e.to]) {
                dist[e.to] = dist[e.from] + e.weight;
                updated = true;
            }
        }

        // 如果这一轮没有更新，提前退出
        if (!updated) break;
    }

    // 检测负环
    for (const Edge& e : edges) {
        if (dist[e.from] != INF && dist[e.from] + e.weight < dist[e.to]) {
            // 存在负环
            return false;
        }
    }

    return true;  // 不存在负环
}

时间复杂度分析

• 时间复杂度：O(VE)，其中V是顶点数，E是边数

SPFA算法

SPFA（Shortest Path Faster Algorithm）是Bellman-Ford的队列优化版本，平均复杂度为O(kE)，k一般很小。

bool spfa(int start, int n) {
    // 初始化
    for (int i = 1; i <= n; i++) {
        dist[i] = INF;
        inQueue[i] = false;
        count[i] = 0;  // 记录顶点入队次数，用于判断负环
    }

    dist[start] = 0;
    queue<int> q;
    q.push(start);
    inQueue[start] = true;
    count[start]++;

    while (!q.empty()) {
        int u = q.front();
        q.pop();
        inQueue[u] = false;

        // 更新u的所有邻居
        for (const Edge& e : graph[u]) {
            int v = e.to;
            int w = e.weight;

            if (dist[u] + w < dist[v]) {
                dist[v] = dist[u] + w;

                if (!inQueue[v]) {
                    q.push(v);
                    inQueue[v] = true;
                    count[v]++;

                    // 如果一个顶点入队次数超过n，说明存在负环
                    if (count[v] > n) {
                        return false;  // 存在负环
                    }
                }
            }
        }
    }

    return true;  // 不存在负环
}

Floyd-Warshall算法

【算法】Floyd-Warshall算法用于解决多源最短路径问题，即求出图中任意两点之间的最短路径。

算法思想

1. 通过三重循环，考虑对于每一对顶点(i,j)，是否存在一个顶点k，使得从i到k再到j的路径比已知的从i到j的路径更短
2. 不断更新这些中间路径，最终得到任意两点间的最短路径

代码实现

const int MAXN = 505;
const int INF = 0x3f3f3f3f;

int dist[MAXN][MAXN];  // 存储任意两点间的最短距离

void floyd(int n) {
    // 初始化，dist[i][j]已经包含了直接连接的边

    // 核心算法：考虑所有可能的中转点
    for (int k = 1; k <= n; k++) {
        for (int i = 1; i <= n; i++) {
            for (int j = 1; 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]);
                }
            }
        }
    }
}

时间复杂度分析

• 时间复杂度：O(V³)
• 空间复杂度：O(V²)

应用场景

1. 需要求解所有点对之间最短路径的场景
2. 图的顶点数不是很大（小于1000）的情况
3. 传递闭包问题

各算法对比与选择

实战技巧

1. 当图没有负权边时，优先使用Dijkstra算法
2. 当顶点数较小（<1000）且需要求所有点对的最短路径时，使用Floyd-Warshall
3. 当存在负权边且顶点数较大时，使用SPFA算法
4. 检测负权环时，使用Bellman-Ford或SPFA算法

常见问题与优化

1. 路径记录：通过添加prev数组记录前驱节点，可以重建最短路径
2. 处理无穷大：使用合适的INF值，避免整数溢出
3. 多起点：对于多个起点的问题，可以添加一个超级源点
4. 启发式优化：针对特定问题，可以结合启发式算法（如A*）

练习题目推荐

1. POJ 3259 Wormholes (负环检测)
2. POJ 1502 MPI Maelstrom (Dijkstra)
3. POJ 3660 Cow Contest (Floyd传递闭包)
4. Codeforces 20C Dijkstra? (路径重建)

通过这些练习题，你可以深入理解和掌握不同最短路径算法的实际应用。