本笔记内容来源于算法基础课

最短路

对于给定$n$个点,$m$条边的图

1. 单源最短路：求一个点到其他所有点的距离
   • 所有边权重均为正数
     • 朴素Dijkstra算法，时间复杂度为$O(n^2)$，与边数无关，适用于稠密图
     • 堆优化版Dijkstra算法，时间复杂度为$O(m\lg n)$
   • 存在边的权重为负数
     • Bellman-Ford，时间复杂度为$O(nm)$，可求不超过$k$条边的最短路
     • SPFA，时间复杂度一般为$O(m)$，最坏为$O(nm)$
2. 多源汇最短路：求任意两点之间的距离
   • Floyd算法，时间复杂度为$O(n^3)$，权重可以为负

若图中存在自环且为正，则自环必不可能存在于1~n的最短路中，因此不需要特殊处理
若可能询问i~i，则需要初始化为0

若图中存在重边，则只需要维护最短的一条边
邻接矩阵：g[i][j] = Integer.min(g[i][j], w)
邻接表则会存储所有边，因此不需要特殊处理

若图中存在负权回路在路径当中，则最小值为$-\infty$

朴素Dijkstra算法

时间复杂度为$O(n^2)$，与边数无关，适用于稠密图

采用邻接矩阵的方式进行图的存储

思想：维护集合$S$，当前已经确定最短距离的点

dist[1] = 0, dist[i] = +infite // 初始化1到其他点的距离
for (i : 1 ~ n-1) // 每循环一次，会确定一个最近点加入到S中，n次就能得到所有点的最短距离
    t <- 不在S中的，距离最近的点
    S <- t
    用t更新其他所有点的距离

每次循环都需要从$n$个点中寻找最近的点，因此时间复杂度为$O(n^2)$

边权存在负数则不能使用Dijkstra

int Inf = 0x3f3f3f3f 定义无穷大
int g[N][N] 存储图
int dist[N] 维护1号点到其他点之间的距离
boolean st[N] 判断点是否已经确定最短路

void Dijkstra() {
    for (int i = 1; i <= n; i++) dist[i] = Inf;
    dist[1] = 0; // 初始化距离
    for (int i = 1; i < n; i++) { // 迭代n-1次 
        int t = -1; // 选取最近点
        for (int j = 1; j <= n; j++) { 
            if (!st[j] && (t == -1 || dist[t] > dist[j]))
                t = j;
        }
        st[t] = true; // 加入集合

        for (int j = 1; j <= n; j++) // 更新到其他点的最短距离
            dist[j] = Integer.min(dist[j], dist[t] + g[t][j]);
    }
}

堆优化版Dijkstra

优化思想： 确定最短距离的点可以使用堆进行优化，查询时间复杂度为$O(1)$

需要对$m$条边的最短路，进行修改调整的时间复杂$m\lg n$

堆的实现方式:

1. 手写堆：可以对堆中任意一个数进行修改，保证堆中始终只有$n$个数
2. 优先队列：不能对堆中任意一个数进行修改，采取冗余插入，堆中最多为$m$个数

PriorityQueue<Node> heap维护小根堆，堆中的节点包括距离和下标

void Dijkstra() {
    for (int i = 1; i <= n; i++) dist[i] = Inf;
    dist[1] = 0; // 初始化距离
    PriorityQueue<Node> heap = new PriorityQueue<>((o1, o2) -> o1.d - o2.d);
    heap.add(new Node(0, 1)); // 初始化堆
    while (heap.size() > 0) {
        Node t = heap.poll(); // 取出最短距离的点

        if (st[t.v]) continue; // 已经是最短距离(因为原先的没有从堆中删除)
        st[t.v] = true;

        for (int i = h[t.v]; i != -1; i = ne[i]) { // 更新它的相邻节点距离
            int j = e[i];
            if (dist[j] > dist[t.v] + w[i]) {
                dist[j] = dist[t.v] + w[i];
                heap.add(new Node(dist[j], j));  // 将更短的距离加入
            }
        }
    }
}

Bellman-Ford算法

思想：不断对所有边进行松弛操作

dist[1] = 0, dist[i] = +infite // 初始化1到其他点的距离
for (i : 1 ~ n) // 迭代n次，每次对所有边进行松弛操作
    for (a -> b, w : 所有边)
        dist[b] = min(dist[b], dist[a] + w) // 松弛操作

迭代次数$k$次：路径不超过$k$条边的最短路

时间复杂度为$O(nm)$

Edge edges[M]使用边数组，因为更新时不需要访问节点的相邻边，直接更新所有边

void Bellman_Ford() {
    for (int i = 1; i <= n; i++) dist[i] = Inf;
    dist[1] = 0;
    for (int i = 0; i < k; i++) {
        int[] backup = dist.clone(); // 备份dist, 因为dist数组在更新时发生修改
        for (int j = 0; j < m; j++) {
            int a = edges[j].a, b = edges[j].b, w = edges[j].w;
            dist[b] = Integer.min(dist[b], backup[a] + w);
        }
    }
}

注意判断是否为正无穷不能直接判断是否等于Inf，因为负权边的存在，可能使得更新为Inf + (-w)，因此可以使用if (dist[n] > Inf / 2)

SPFA算法

优化思想：每当某个节点的dist变小，更新其所有的相邻节点

使用队列维护所有需要更新相邻节点的节点

dist[1] = 0, dist[i] = +infite // 初始化1到其他点的距离
while(queue 不空) 
    t <- q.poll()
    更新所有相邻节点
    将更新成功的点加入到队列中

void SPFA() {
    for (int i = 1; i <= n; i++) dist[i] = Inf;
    dist[1] = 0;
    Deque<Integer> q = new ArrayDeque<>();
    q.offerLast(1);
    st[1] = true; // 防止队列中节点被重复加入，保证队列中至多为图的n个节点
    while (q.size() > 0) {
        int t = q.pollFirst();
        st[t] = false;
        for (int i = h[t]; i != -1; i = ne[i]) {
            int j = e[i];
            if (dist[j] > dist[t] + w[i]) {
                dist[j] = dist[t] + w[i];
                if (!st[j]) {
                    q.offerLast(j);
                    st[j] = true;
                }
            }
        }
    }
}

也可以使用循环队列模拟，循环队列中最多包含$n$个节点

void SPFA() {
    for (int i = 1; i <= n; i++) dist[i] = Inf;
    dist[1] = 0;
    q[tt++] = 1;
    st[1] = true;
    while (hh <= tt) {
        int t = q[hh++];
        if (hh == N) hh = 0;
        st[t] = false;
        for (int i = h[t]; i != -1; i = ne[i]) {
            int j = e[i];
            if (dist[j] > dist[t] + w[i]) {
                dist[j] = dist[t] + w[i];
                if (!st[j]) {
                    q[tt++] = j;
                    if (tt == N) tt = 0;
                    st[j] = true;
                }
            }
        }
    }
}

判断负环

cnt[N] 表示当前最短路边的数量

在更新最短距离时dist[x] = dist[t] + w[i], 说明最短路径发生了变化，因此cnt[x] = cnt[t] + 1

图中有$n$个点，则不经过相同点的路径最长为$n - 1$。因此当cnt[x] >= n时，说明路径中存在两个相同的点 ，所以路径中存在环。

而由于SPFA求的是最短路，因此该环必然是负环，否则不可能在最短路上

boolean SPFA() {
    // 距离不需要初始化，因为若存在负环则必然会不断更新距离，使得两点之间距离为负无穷
    for (int i = 1; i <= n ; i++) { // 队列初始不能只存1，可能1不可达到其他点，例如图不连通
        st[i] = true;
        q[tt++] = i;
    }
    while (hh != tt) {
        int t = q[hh++];
        if (hh == N) hh = 0;
        st[t] = false;
        for (int i = h[t]; i != -1; i = ne[i]) {
            int j = e[i];
            if (dist[j] > dist[t] + w[i]) {
                dist[j] = dist[t] + w[i];
                cnt[j] = cnt[t] + 1;
                if (cnt[j] >= n) return true;
                if (!st[j]) {
                    q[tt++] = j;
                    if (tt == N) tt = 0;
                    st[j] =true;
                }
            }
        }
    }
    return false;
}

Floyd算法笔记

思想：使用中转点进行松弛操作

d[i, j]存储i到j的距离

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] = Integer.min(d[i][j], d[i][k] + d[k][j]);
}

注意：
1. 初始化距离i -> i初始化为0，其他为Inf
2. 存在重边因此维护最小的边
3. 因为存在负权边，最后判断采用if (d[a][b] > Inf / 2)