考研算法辅导课笔记（十）

最短路

最短路一般分为单源最短路和多源汇最短路。

源点也就是起点，汇点也就是终点。

最短路问题的考察重点在于如何将问题抽象建图，而不在算法的正确性。（说白了多背模板）

最短路问题不考虑有向图和无向图的区别，因为无向图就是一种特殊的有向图。

其中n表示点数，m表示边数。

稠密图(m~n^2同一级别)用朴素版的Dijkstra算法，稀疏图(m~n同一级别)用堆优化版的Dijkstra算法。

注：在考研408数据结构中，不考察单源最短路中的存在负权边的两种算法！

Dijkstra算法

它和prim算法很像，也分为朴素版和堆优化版两个版本。

用来求有权图的单源最短路径的算法，基于贪心思想。

这种算法只适用于非负权图，但是时间复杂度非常优秀。

acwing.849. Dijkstra求最短路 I

给定一个 n 个点 m 条边的有向图，图中可能存在重边和自环，所有边权均为正值。
请你求出 1 号点到 n 号点的最短距离，如果无法从 1 号点走到 n 号点，则输出 −1。

输入格式
第一行包含整数 n 和 m。
接下来 m 行每行包含三个整数 x,y,z，表示存在一条从点 x 到点 y 的有向边，边长为 z。

输出格式
输出一个整数，表示 1 号点到 n 号点的最短距离。
如果路径不存在，则输出 −1。

数据范围
1≤n≤500,
1≤m≤10^5,
图中涉及边长均不超过10000。

输入样例：
3 3
1 2 2
2 3 1
1 3 4
输出样例：
3

题解参考算法基础课笔记（十八）。

一篇非常全面的题解。

存储方式：朴素版Dijkstra 算法适用于稠密图，而稠密图一般用邻接矩阵来存储。

时间复杂度：O(n^2+m)。

写法和prim算法非常相似。可以对比一下，两个算法的差别基本只有对dist[N]数组的更新方式的区别。

要注意的一点就是dijkstra输出的答案不需要累加，d[N]维护的就是起点到每个点的最短距离。

注意一下方向，这是有向图。

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 505,INF = 0x3f3f3f3f;
int n,m;
int g[N][N],di[N];
bool st[N];

int dijkstra(){
    memset(di,0x3f,sizeof di);
    
    di[1] = 0;
    for (int i = 1;i <= n;i ++){
        int t = -1;
        for (int j = 1;j <= n;j ++)
            if (!st[j] && (t == -1 || di[t] > di[j]))
                t = j;
        
        if (di[t] == INF) return INF;
        st[t] = true;
        
        for (int j = 1;j <= n;j ++) // 集合里每加入一个点，就进行一轮边松弛
            di[j] = min(di[j],di[t] + g[t][j]); // 注意g[t][j]顺序不能反！
    }
    return di[n];
}

int main(){
    memset(g,0x3f,sizeof g);
    cin >> n >> m;
    
    int a,b,c;
    while (m--){
        cin >> a >> b >> c;
        g[a][b] = min(g[a][b],c);
    }
    
    int t = dijkstra();
    if (t == INF) cout << -1;
    else cout << t;
    return 0;
}

Floyd 算法

是用来求任意两个结点之间的最短路的，利用DP思想。

复杂度比较高，但是常数小，容易实现，也可以处理负权边。效率比执行 n次 Dijkstra 算法要好。

f[k,i,j]代表（k的取值范围是从1到n），在考虑了从1到k的节点作为中间经过的节点时，从i到j的所有路径的最小值。

形式化说明如下：

f[k][i][j]可以从两种情况转移而来：
【1】从f[k−1][i][j]转移而来，表示i到j的最短路径不经过k这个节点
【2】从f[k−1][i][k]+f[k−1][k][j]转移而来，表示i到j的最短路径经过k这个节点

那么f[k,i,j] = min(f[k-1,i,j], f[k-1,k,i] + f[k-1,k,j])。

因此在计算第k层的f[i,j]的时候必须先将第k - 1层的所有状态计算出来，所以需要把k放在最外层。

可以把k这一维度去掉，降低空间复杂度，f[i,j] = min(f[i,j], f[i,k] + f[k,j])。

acwing.854. Floyd求最短路

给定一个 n 个点 m 条边的有向图，图中可能存在重边和自环，边权可能为负数。
再给定 k 个询问，每个询问包含两个整数 x 和 y，表示查询从点 x 到点 y 的最短距离，如果路径不存在，则输出 impossible。
数据保证图中不存在负权回路。

输入格式
第一行包含三个整数 n,m,k。
接下来 m 行，每行包含三个整数 x,y,z，表示存在一条从点 x 到点 y 的有向边，边长为 z。
接下来 k 行，每行包含两个整数 x,y，表示询问点 x 到点 y 的最短距离。

输出格式
共 k 行，每行输出一个整数，表示询问的结果，若询问两点间不存在路径，则输出 impossible。

数据范围
1≤n≤200,
1≤k≤n^2
1≤m≤20000,
图中涉及边长绝对值均不超过 10000。

输入样例：
3 3 2
1 2 1
2 3 2
1 3 1
2 1
1 3
输出样例：
impossible
1

题解参考算法基础课笔记（二十）。

一篇DP原理解析的题解。

#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int N = 205,INF = 0x3f3f3f3f;
int d[N][N];
int n,m,k;

void floyd(){
    for (int k = 1;k <= n;k ++)
        for (int i = 1;i <= n;i ++)
            for (int j = 1;j <= n;j ++) // 三维DP，状态转移方程
                d[i][j] = min(d[i][j],d[i][k]+d[k][j]);
}

int main(){
    cin >> n >> m >> k;
    
    memset(d,0x3f,sizeof d);
    for (int i = 1;i <= n;i ++) d[i][i] = 0;
    
    int a,b,c;
    while (m--){
        cin >> a >> b >> c;
        d[a][b] = min(d[a][b],c);
    }
    
    floyd();
    int x,y;
    while (k--){
        cin >> x >> y;
        if (d[x][y] > INF / 2) cout << "impossible\n";
        else cout << d[x][y] << '\n';
    }
    return 0;
}

Floyd和BF算法类似，会遍历所有的边，因此不管是不是和源点连通的边它都会得到更新，因此就算不存在x到y的最短路，距离INF会发生改变，但不至于超过一半，所以用INF/2来判断。

关键路径

简单示例参考博客；详细内容（废话）参考王道P234；代码实现与算法讲解参考算法笔记P417。

补充概念：

有向无环图简称为DAG图。用DAG图表示的工程网络称之为AOV网。

带权DAG图表示的工程网络称之为AOE网。AOE也就是一个拓扑图。

AOE网的边有权值，AOV网的边无权值。

关键路径是AOE网中的概念。

事件是点，活动是边！

在AOE网中，所有活动都完成才能到达终点，因此完成整个工程所必须花费的时间（即最短工期）应该为源点到终点的最大路径长度。具有最大路径长度的路径称为关键路径。关键路径上的活动称为关键活动。

关键路径并不唯一！

ETV(Earliest Time Of Vertex)：事件最早发生时间，就是顶点的最早发生时间；

事件k的ETV指的是从源点到顶点k的最长路径长度。源点的ETV等于0。
LTV(Latest Time Of Vertex)：事件最晚发生时间，就是每个顶点对应的事件最晚需要开始的时间；

事件k的LTV指的是汇点的LTV与从顶点k到汇点的最长路径长度之差。汇点的LTV等于汇点的ETV。
ETE(Earliest Time Of Edge)：活动的最早开工时间，就是边的最早发生时间，就是边起点的最早发生时间；
LTE(Lastest Time of Edge)：活动的最晚发生时间，就是边终点的最晚发生时间与该活动时间之差。