图：最短路径算法（Shortest Path Algorithms）

一、单源最短路径问题 (Single-Source Shortest-Path Problem)

1. 问题定义

给定一个加权有向图 \( G = (V, E) \)，其中：

• \( V \) 是顶点集
• \( E \) 是边集
• 每条边 \( e \in E \) 有一个权重（成本）函数 \( c(e) \)
• 指定一个起点顶点 \( s \)

目标：找到从 \( s \) 到图中每个其他顶点的最短加权路径。

路径长度：对于从起点到终点的路径 \( P \)，其长度定义为路径上所有边的权重之和：

注意：

• 如果图中存在 负权环（negative-cost cycle），最短路径可能不存在（因为可以无限循环降低路径成本）。
• 若无负权环，从 \( s \) 到自身的路径长度定义为 0。

• 在带权图中，对于任意三个顶点 \( u \)、\( v \)、\( w \)，最短路径满足：

  \[ \text{dist}(u, w) \leq \text{dist}(u, v) + \text{dist}(v, w) \]

其中 \( \text{dist}(x, y) \) 表示 \( x \) 到 \( y \) 的最短路径长度。

2. 示例图

PPT 中给出了两个示例有向图，展示正权和负权边的情况：

负权边示例：边 \( v2 \to v5 \) 的权重从 10 变为 -10，可能影响最短路径计算。

二、无权最短路径算法 (Unweighted Shortest Paths)

1. 核心思想

无权图中，边的权重均视为 1，因此最短路径等价于 最少边数 的路径。采用 广度优先搜索 (BFS) 的思想，按距离递增的顺序探索顶点。

2. 数据结构

使用一个表Table[i]存储每个顶点 \( v_i \) 的信息：

• Dist：从起点 \( s \) 到 \( v_i \) 的距离（初始为 \( \infty \)，起点为 0）
• Known：是否已确定最短路径（1 为已确定，0 为未确定）
• Path：记录路径上的前驱顶点（初始为 0）

3. 基本算法

以下是无权最短路径的伪代码实现：

void Unweighted(Table T) {
    int CurrDist;
    Vertex V, W;
    for (CurrDist = 0; CurrDist < NumVertex; CurrDist++) {
        for (each vertex V) {
            if (!T[V].Known && T[V].Dist == CurrDist) {
                T[V].Known = true;
                for (each W adjacent to V) {
                    if (T[W].Dist == Infinity) {
                        T[W].Dist = CurrDist + 1;
                        T[W].Path = V;
                    }
                }
            }
        }
    }
}

算法步骤：

• 从距离 0 开始（即起点 \( s \)），逐层处理距离为 \( CurrDist \) 的顶点。
• 对于每个未处理（Known = 0）且距离为 \( CurrDist \) 的顶点 \( V \)：
  • 标记为已处理（Known = true）。
  • 检查 \( V \) 的所有邻接顶点 \( W \)，若 \( W \) 的距离为 \( \infty \)，更新为 \( CurrDist + 1 \)，并记录前驱为 \( V \)。

时间复杂度：

• 最坏情况：\( O(|V|^2) \)，因为需要扫描所有顶点多次。
• 适合稠密图。

4. 改进版算法（基于队列）

通过使用队列优化，减少不必要的扫描：

void Unweighted(Table T) {
    Queue Q;
    Vertex V, W;
    Q = CreateQueue(NumVertex);
    MakeEmpty(Q);
    Enqueue(S, Q); /* Enqueue the source vertex */
    while (!IsEmpty(Q)) {
        V = Dequeue(Q);
        T[V].Known = true; /* optional */
        for (each W adjacent to V) {
            if (T[W].Dist == Infinity) {
                T[W].Dist = T[V].Dist + 1;// 加1是因为无权，边都视为1
                T[W].Path = V;
                Enqueue(W, Q);
            }
        }
    }
    DisposeQueue(Q);
}

改进点：

• 使用队列 \( Q \) 存储待处理的顶点，从起点 \( s \) 开始。
• 出队顶点 \( V \)，处理其邻接顶点 \( W \)，若 \( W \) 未访问（Dist = \( \infty \)），更新距离并入队。

时间复杂度：

• \( O(|V| + |E|) \)，因为每个顶点入队一次，每条边处理一次。
• 适合稀疏图。

三、Dijkstra 算法 (Weighted Shortest Paths)

1. 核心思想

Dijkstra 算法用于 非负权边 的加权图，采用 贪心策略，每次选择距离起点最近的未处理顶点，更新其邻接顶点的距离。

关键概念：

• \( S \): 已找到最短路径的顶点集合（初始为 \( \{s\} \)）。

• \( distance[u] \): 从 \( s \) 到 \( u \) 的最短路径长度（仅通过 \( S \) 中的顶点）。

  \[ distance'[u_2] = distance[u_1] + c(u_1, u_2) \]

更新规则：若发现通过新加入的顶点 \( u_1 \) 到 \( u_2 \) 的路径更短，则更新。

2. 伪代码实现

#define inf 999999
#define MAX 100007
bool visited[MAX] = {false};
//源顶点S
int s;
void Dijkstra(Graph *G,int s){
    //创建优先队列
    Queue *q;
    //初始化队列
    InitQueue( q );
    int distance[MAX], i;
    //for(i = 0;i <= MAX;i ++){
        if(i != s){
            //如果不是源顶点，就赋值为“无穷大”，
            distance[i] = inf;
        }else{
            distance[i] = 0;
            visited[i] = true;
        }
    //}
    //w就是新邻居捏
    int w, new_distance;

    //s入队列
    EnQueue(q, s);
    visited[s] = true;
    //IsEmpty判断队列是否为空
    while( !IsEmpty(q) ){
        v = DeQueue(q);
        //FirstNeighbor(G, v):求图G中顶点v的第一个邻接点，
        //若有则返回顶点号，否则返回-1。
        //NextNeighbor(G, v, w):假设图G中顶点w是顶点v的一个邻接点，返回除w和已访问外的顶点v
        for(w = FirstNeighbor(G, v);w >= 0;w = NextNeighbor(G, v, w)){
            //calculate_distance实现两顶点间权的读取
            new_distance = calculate_distance(v, w) + distance[v];
            if(new_distance <= distance[w]){
                distance[w] = new_distance;
            }
            if(visited[w] == false) {
                visited[w] = true;
                EnQueue(w);
            }
        }
    }
}

算法步骤：由于是单源，所以记源顶点为S。

1. 初始化

   • 创建一个集合visited，这个是记录已经找到最短路径的节点。开始时，初始化为空的就好。
   • 创建一个优先队列（如最小堆），将源节点加入队列。
   • 创建一个数组distance[i]，用于存储从源节点到其他节点的当前已知最短距离。将distance[S]初始化为0；将优先队列中的顶点对应的距离，设置为源到该顶点的权重；而除优先队列以外的其他所有节点的距离初始化为无穷大。

2. 从优先队列中取出相邻距离最小的节点

   • 从优先队列中取出相邻距离最小的节点u。（如果队列为空，则算法结束。）
   • 将节点u标记为已访问（将其添加到visited集合中）。

3. 更新未访问邻居的距离：遍历节点u的所有邻居v，如果distance[v]是无穷大或其他值，则有：

   • 计算通过节点u到达节点v的距离，即new_distance = distance[u] + weight(u, v)。
   • 如果new_distance小于当前已知的distance[v]，则更新distance[v]为new_distance。
   • 如果节点v尚未在优先队列中，或者其当前优先级高于新计算的距离，则将节点v（及其新距离）加入优先队列。

4. 重复：重复步骤2和3，直到优先队列为空，即所有节点都已从队列中取出并被标记为已访问。

5. 结果：distance[]数组现在得到了从源节点到图中所有其他节点的最短距离。

限制：不适用于负权边（可能导致错误结果）。

3. 时间复杂度

• 实现 1：每次扫描表选择最小距离顶点，复杂度 \( O(|V|) \)。（适合稠密图）

  • 初始化：设置 \( V \) 个顶点的距离，时间复杂度为 \( O(V) \)。

  • 选择最小距离顶点：每次需要扫描所有未处理顶点，初始时有 \( V \) 个顶点，之后逐个减少。总共执行 \( V \) 次选择，第一次扫描 \( V \) 个元素，第二次扫描 \( V-1 \) 个，……，最后一次扫描 1 个。总扫描次数为：

    \[ \sum_{i=1}^{V} i = \frac{V (V + 1)}{2} = O(V^2) \]

  • 更新距离：每次处理一个顶点 \( u \) 时，检查其所有邻接顶点。每个顶点最多被处理一次，边数为 \( E \)，因此总更新操作的次数为 \( O(E) \)。每次更新是 \( O(1) \) 的，因此总时间为 \( O(E) \)。

  • 总时间复杂度：\( O(V^2 + E) \)。在稀疏图中（\( E \) 远小于 \( V^2 \)），主项为 \( O(V^2) \)；在稠密图中（\( E \approx V^2 \)），复杂度仍为 \( O(V^2) \)。

• 实现 2：使用优先队列（如最小堆）。（适合稀疏图）

  • 初始化：将所有 \( V \) 个顶点插入优先队列，时间复杂度为 \( O(V) \)。
  • 提取最小元素：每次从二叉堆中提取最小元素，操作时间复杂度为 \( O(\log V) \)。总共执行 \( V \) 次，时间复杂度为 \( O(V \log V) \)。
  • 减少键值（更新距离）：每次处理一个顶点时，可能需要更新其所有邻接顶点的距离。每个顶点最多被处理一次，边数为 \( E \)，因此减少键值操作的总次数不超过 \( E \)。在二叉堆中，减少键值的时间复杂度为 \( O(\log V) \)，总时间复杂度为 \( O(E \log V) \)。
  • 总时间复杂度：\( O((V + E) \log V) \)，其中 \( V \) 是顶点数，\( E \) 是边数。

• 实现 3：使用斐波那契堆。（适合稠密图）

  • 初始化：将 \( V \) 个顶点插入斐波那契堆，时间复杂度为 \( O(V) \)。
  • 提取最小元素：每次提取最小元素，均摊时间复杂度为 \( O(\log V) \)。总共执行 \( V \) 次，时间复杂度为 \( O(V \log V) \)。
  • 减少键值（更新距离）：斐波那契堆的减少键值操作的均摊时间复杂度为 \( O(1) \)。由于每个顶点可能触发最多 \( E \) 次减少键值操作（对应图中的边），总时间复杂度为 \( O(E) \)。
  • 总时间复杂度：\( O(V \log V + E) \)，其中均摊分析确保了减少键值的 \( O(1) \) 优势。

四、负权边处理 (Graphs with Negative Edge Costs)

1. 简单想法的失败

• 错误方案：将所有边权重加上一个常数 \( \Delta \) 以消除负权边。
• 问题：改变路径权重比例（比如有的最短路径要走3条边，而有的只走2条，每条边加一个常数显然是不对的），可能导致最短路径变化。

2. 负权边算法

void WeightedNegative(Table T) {
    Vertex V, W;                // V 和 W分别表示当前处理的顶点和其邻接顶点
    Queue Q = CreateQueue(NumVertex); // 创建一个队列 Q
    MakeEmpty(Q);               // 清空队列 Q，准备使用
    Enqueue(S, Q);              // 将源点 S 入队，作为起点开始松弛
    while (!IsEmpty(Q)) {       // 当队列非空时，持续执行松弛操作
        V = Dequeue(Q);         // 从队列头部取出当前处理的顶点 V
        for (each W adjacent to V) { // 遍历 V 的所有邻接顶点 W
            if (T[V].Dist + Cvw < T[W].Dist) { // 如果通过 V 到 W 的距离小于当前 T[W].Dist
                T[W].Dist = T[V].Dist + Cvw; // 更新 W 的距离为 V 的距离加上边权重 Cvw
                T[W].Path = V;         // 更新 W 的前驱为 V
                if (W is not already in Q) // 如果 W 不在队列中
                    Enqueue(W, Q);      // 将 W 入队，以便后续松弛其邻接顶点
            }
        }
    }
    DisposeQueue(Q);            // 释放队列 Q 的内存
}

时间复杂度：\( O(|V| \cdot |E|) \)，适合稀疏图。

五、无环图最短路径 (Acyclic Graphs)

若图是 无环图（DAG），可按 拓扑排序 顺序处理顶点。

时间复杂度：\( O(|V| + |E|) \)。

六、全对最短路径问题 (All-Pairs Shortest Path Problem)

• 方法 1：对每个顶点运行单源最短路径算法。
  • 时间复杂度：\( O(|V|^3) - \text{works fast on sparse graph} \)。
• 方法 2：Floyd-Warshall 算法。
  • 时间复杂度：\( O(|V|^3) \)。