最短路问题

目录

1. 单源最短路

2. 所有边权都是正数

3. 存在负权边

4. 多源汇最短路

单源最短路

一.所有边权都是正数

算法1：朴素Dijkstra ( $O(n^2)$)

算法步骤：

1. 初始化：
2. 为每个顶点分配一个距离值，初始时，起点的距离设为0，其他顶点的距离设为无穷大（表示尚未被访问）。
3. 选择最短路径顶点：
4. 每次从未处理的顶点集合中选出距离值最小的顶点，称为“当前顶点”。
5. 从集合中标记该顶点，表示已确定其最短路径。
6. 更新邻接顶点的距离：
7. 对当前顶点的每一个邻接顶点，如果通过当前顶点可以获得更短的路径，则更新该邻接顶点的距离值。
8. 重复步骤2和3：
9. 直到所有顶点都已确定最短路径，或目标顶点的最短路径已确定为止。

稠密图版本：

int g[N][N]; // 邻接矩阵存图
int dis[N]; // 存到对应点的最短距离
bool vis[N]; // 标记确定最短路的点

int dijkstra(){
    memset(dis, 0x3f, sizeof dis); // 初始化距离为无穷大
    dis[1] = 0; // 起点到起点距离为0

    for(int i = 0; i < n - 1; i ++){
        int t = -1; // dis[-1] = 0x3f3f3f3f;
        for(int j = 1; j <= n; j ++){ // 寻找未处理点中距离值最小的点
            if(!vis[j] && (t == -1 || dis[t] > dis[j]))
                t = j;
        }

        vis[t] = true; // 标记确定最短路的点

        for(int j = 1; j <= n; j ++){ // 根据新点更新距离
            dis[j] = min(dis[j], dis[t] + g[t][j]);
        }
    }
    if(dis[n] == 0x3f3f3f3f) return -1;
    return dis[n];
}

int main(){
    memset(g, 0x3f, sizeof g); // 求最短路, 初始化图边权无穷大
    ......
}

邻接表版本

int dis[N]; // 存到对应点的最短距离
bool vis[N]; // 标记确定最短路的点

// 邻接表存图
int h[N], e[M], ne[M], w[M], idx; // 邻接表存图
void add(int a, int b, int c){
    e[idx] = b;
    ne[idx] = h[a];
    w[idx] = c;
    h[a] = idx ++;
}

int dijkstra(){
    ··· // 与上相同，就更新距离部分有改动
    for(int j = h[t]; j != -1; j = ne[j]){
        int p = e[j];
        dis[p] = min(dis[p], dis[t] + w[j]);
    }
}

int main(){
    memset(h, -1, sizeof h);
    ......
}

算法2：堆优化版Dijkstra ( $O(mlogn)$)

原理：对朴素Dijkstra算法进行优化 [HTML_REMOVED](优化方式：堆优化)[HTML_REMOVED]

1. 初始化改进：将起点加入到一个未处理的顶点集合中（通常使用优先队列或最小堆实现，以便[HTML_REMOVED]快速找到当前距离最小的顶点[HTML_REMOVED]）。
2. 选择最短路径顶点：
3. 每次从未处理的顶点集合中选出[HTML_REMOVED]距离值最小的顶点[HTML_REMOVED]，称为“当前顶点”。
4. 从集合中移除该顶点，表示已确定其最短路径。
5. 更新邻接顶点的距离：
6. 对当前顶点的每一个邻接顶点，如果通过当前顶点可以获得更短的路径，则更新该邻接顶点的距离值，[HTML_REMOVED]并将其加入未处理的顶点集合中[HTML_REMOVED]。
7. 重复步骤2和3

typedef pair<int, int> PII;

int dis[N]; // 记录某点最短路
bool vis[N]; // 标记确定最短路的点

int h[N], e[M], ne[M], w[M], idx; // 邻接表
void add(int a, int b, int c){ // 邻接表存边
    e[idx] = b;
    ne[idx] = h[a];
    w[idx] = c;
    h[a] = idx ++;
}

int dijkstra(){
    memset(dis, 0x3f, sizeof dis); // 初始化距离为无穷大
    dis[1] = 0; // 起点距离为0
    priority_queue<PII, vector<PII>, greater<PII>> heap; // 小根堆(根据距离排序，找出最近点)
    heap.push({0, 1}); // 存入起点(距离，编号)

    while(heap.size()){
        auto t = heap.top(); // 当前距离最近点
        heap.pop();

        int ver = t.second, distance = t.first; // 当前点编号, 距离

        if(vis[ver]) continue;
        vis[ver] = true; // 标记

        for(int i = h[ver]; i != -1; i = ne[i]){ // 更新
            int j = e[i];
            if(dis[j] > dis[ver] + w[i]){
                dis[j] = dis[ver] + w[i];
                heap.push({dis[j], j}); // 存入下一个点进行更新
            }
        }
    }

    if(dis[n] == 0x3f3f3f3f) return -1;
    return dis[n];
}

int main(){
    memset(h, -1, sizeof h);
    ......
}

二.存在负权边

算法1：Bellman-Ford算法

Bellman-Ford算法是一种用于计算单源最短路径的经典算法，能够处理带有负权边的图。它的主要优点是可以检测到图中的负权回路。

算法步骤：

1. 初始化：

2. 设定源点为 s，将源点的距离初始化为 0，其他所有点的距离初始化为正无穷。

3. 设定一个数组 dis[]，用于存储从源点到各顶点的最短距离。

4. 松弛操作：

5. 对每条边 (u, v) 进行松弛操作，即检查通过边 (u, v) 是否可以让 dis[v] 的值变得更小，公式为：

   if (dis[u] + w(u, v) < dis[v]) dis[v] = dis[u] + w(u, v)

6. 这里，w(u, v) 是边 (u, v) 的权重。

7. 重复松弛操作：

8. 在一个图中，最多需要对所有的边进行 V-1 次松弛操作（V 是图中的顶点数）。因为一个最短路径最多会包含 V-1 条边。

9. 检查负权回路：

10. 在执行完 V-1 轮松弛操作后，再进行一次松弛操作，如果仍然能够减少某个点的距离，则说明存在负权回路。

int n, m, k;
int dis[N];
// int pre[N]; // 备份数组

struct Edge{
    int a, b, w;
} edges[M];

void bellman_ford(){
    memset(dis, 0x3f, sizeof dis);
    dis[1] = 0;

    // 如果第n次迭代仍然会松弛三角不等式，就说明存在一条长度是n+1的最短路径，由抽屉原理，路径中至少存在两个相同的点，说明图中存在负权回路。
    for(int i = 0; i < n; i ++){
        // memcpy(pre, dis, sizeof dis);
        for(int j = 0; j < m; j ++){ // 遍历所有边
            int a = edges[j].a, b = edges[j].b, w = edges[j].w;
            if(dis[b] > dis[a] + w){
                dis[b] = dis[a] + w;
            }
            // dis[b] = min(dis[b], pre[a] + w); // 防止串联更新
        }
    }
}

int main(){
    ...
    if(dis[n] > 0x3f3f3f3f / 2) cout << "impossible" << '\n';
    else cout << dis[n] << '\n';
}

算法2：SPFA算法（队列优化的Bellman-Ford算法）

原理：

1. 基于队列：SPFA 使用一个队列来存储那些“可能”能够被松弛的顶点，即那些需要继续更新的顶点。相比 Bellman-Ford 算法中每轮对所有边进行松弛，SPFA 只对队列中的顶点执行松弛操作，节省了时间。

2. 动态松弛：SPFA 在松弛时只处理那些距离刚刚被更新的顶点，并将这些顶点的邻居加入队列以备后续松弛，直到队列为空。这个过程动态地控制哪些顶点需要被松弛，减少了不必要的操作。

3. 负环检测：如果某个顶点进入队列的次数超过 V-1（V 是顶点数），则可以判断图中存在负权回路，因为最短路径最多只能经过 V-1 条边。如果有一个顶点反复被松弛超过这个次数，说明该顶点可能处于一个负权回路中。

spfa判断图中是否存在负环

int n; // 总点数
int h[N], e[N], ne[N], w[N], idx;
int dis[N];
bool vis[N]; // 存储每个点是否在队列中

int spfa(){
    memset(dis, 0x3f, sizeof dis);
    dis[1] = 0;

    queue<int> q;
    q.push(1);
    vis[1] = true;

    while(q.size()){
        auto t = q.front();
        q.pop();

        vis[t] = false;

        for(int i = h[t]; i != -1; i = ne[i]){
            int j = e[i];
            if(dis[j] > dis[t] + w[i]){
                dis[j] = dis[t] + w[i];
                if(!vis[j]){ // 如果队列中已存在j，则不需要将j重复插入
                    q.push(j);
                    vis[j] = true;
                }
            }
        }
    }

    if (dist[n] == 0x3f3f3f3f) return -1;
    return dist[n];
}

spfa判断图中是否存在负环

int n; // 总点数
int h[N], e[N], ne[N], w[N], idx;
int dis[N], cnt[N]; // dis[x]存储1号点到x的最短距离，cnt[x]存储1到x的最短路中经过的点数
bool vis[N]; // 存储每个点是否在队列中

// 如果存在负环，则返回true，否则返回false。
bool spfa(){
    // 不需要初始化dist数组
    // 原理：如果某条最短路径上有n个点（除了自己），那么加上自己之后一共有n+1个点，由抽屉原理一定有两个点相同，所以存在环。

    queue<int> q;
    for(int i = 1; i <= n; i ++ ){
        q.push(i);
        vis[i] = true;
    }

    while(q.size()){
        auto t = q.front();
        q.pop();

        vis[t] = false;

        for(int i = h[t]; i != -1; i = ne[i]){
            int j = e[i];
            if(dis[j] > dis[t] + w[i]){
                dis[j] = dis[t] + w[i];
                cnt[j] = cnt[t] + 1;
                if(cnt[j] >= n) return true; // 如果从1号点到x的最短路中包含至少n个点（不包括自己），则说明存在负环
                if(!vis[j]){
                    q.push(j);
                    vis[j] = true;
                }
            }
        }
    }

    return false;
}

多源汇最短路

Floyd算法

思想：

Floyd算法的核心思想是通过引入一个中间顶点集来逐步更新所有顶点对之间的最短路径。其基本操作是松弛，即对于任意两点 i 和 j，检查是否通过某个中间顶点 k 可以找到比当前已知路径更短的路径。如果发现新的更短路径，则更新该路径的长度。

// 初始化：
    for (int i = 1; i <= n; i ++ )
        for (int j = 1; j <= n; j ++ )
            if (i == j) d[i][j] = 0;
            else d[i][j] = INF;

void floyd(){
    for(int k = 1; k <= n; k ++)
        for(int i = 1; i <= n; i ++)
            for(int j = 1; j <= n; j ++)
                d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
}