源点：图中的起点； 汇点：图中的终点

单源最短路

单源，顾名思义就是图中只有一个起点。

所有边权都是正数

Dijkstra

$Dijkstra$求最短路问题，需要记录额外两个变量:

int dis[N];        // 当前节点到源点的最短路径距离
bool vis[N];       // 当前节点到源点的最短路径是否已经确定

$Dijkstra$算法是基于贪心的思想，适用于求所有边权都是正数的最短路径。

step1：初始化距离：起点到起点的距离为0，其它点到起点的距离为正无穷。

#include <cstring>
// 初始化距离
memset(dis, 0x3f, sizeof dis);
dis[1] = 0;       // 源点到源点的距离为0，一般题目的源点都是1号点

step2： 循环松弛，每次确定一个点到起点的最短路，在没有确定的点中选取一个距离起点最短的点加入到当前路径。然后用该点去更新其它未确定的点到起点的距离。

总结一下，Dijkstra算法的流程就是，不断取出离顶点最近而没有被访问过的点，松弛它和它能到达的所有点。

朴素版Dijkstra(${O(n^2}$))

适用于稠密图，用邻接矩阵存储。

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 500 + 7;

int graph[N][N];
int dis[N]; bool vis[N];

int n, m;

int dijkstra() {
    // 初始化距离
    memset(dis, 0x3f, sizeof dis);
    memset(vis, 0, sizeof vis);
    dis[1] = 0;
    
    for (int i = 0; i < n; i ++) {
        // 初始化t为-1;
        int u = -1;
        
        // 选择t = dist[j]最小的边
        for (int v = 1; j <= n; j ++) {
            if(!vis[j] && (t == -1 || dis[t] > dis[j])) {
                u = j;
            }
        }
        // t加入已访问集合
        vis[u] = true;
        
        // 用t更新其它点到源点的距离
        for (int v = 1; v <= n; v ++) {
            if(!vis[v]) {
                dis[v] = min(dis[v], dis[u] + graph[u][v]);
            }
        }
    }
    
    if (dis[n] == 0x3f3f3f3f) return -1;
    return dis[n];
}

int main() {
    memset(graph, 0x3f, sizeof graph);
    
    cin >> n >> m;
    for (int i = 1; i <= m; i++)
        int u, v, w;
        scanf("%d %d %d", &u, &v, &w);
        // 两点之间如果存在多条重边，只保留距离最短的那条
        graph[u][v] = min(graph[u][v], w);
        // 如果存在自环，其距离为正显然不用管
    }
    
    cout << dijkstra() << endl;
    
    return 0;
}

练习eg:

AcWing849.Dijkstra求最短路 I

堆优化版Dijkstra(${O(mlog(n)}$))

适用于稀疏图，用邻接表存储。稠密图也可以存，比较通用。

每次选取一个距离起点最短的点⇔多次取最小，然后删除当前最小⇔小根堆

#include <queue>
#include <iostream>
#include <cstring>

using namespace std;

typedef pair<int, int> PII;

const int N = 1e5 + 7;
const int M = 1e6 + 7;

struct Edge{
    int to;
    int w;
    int nxt;
};

Edge edge[M];
int head[N], idx = 1;
int dis[N], vis[N];   // dijk
int n, m;

inline void add(int from, int to, int w) {
    edge[idx].to = to, edge[idx].w = w, edge[idx].nxt = head[from];
    head[from] = idx ++;
}

int dijkstra() {
    // step1: 初始化dis, vis
    memset(dis, 0x3f, sizeof dis); 
    memset(vis, 0, sizeof vis);   
    dis[1] = 0;
    
    // 小根堆
    priority_queue<PII, vector<PII>, greater<PII>> pq;
    pq.push({0, 1});
    
    while(!pq.empty()) {
        int u = pq.top().second; pq.pop();
        
        if (vis[u]) continue;
        vis[u] = true;
        
        int du = dis[u];
        // step2: 循环松弛，遍历head[u]，更新该节点指向的所有结点的dis[]
        for(int i = head[u]; ~i; i = edge[i].nxt) {
            int v = edge[i].to, w = edge[i].w;
            if (dis[v] > du + w) {
                dis[v] = du + w;
                pq.push({dis[v], v});
            }
        }
    }
    
    if (dis[n] == 0x3f3f3f3f) return -1; // 不可达 
    return dis[n];
}


int main() {
    memset(head, -1, sizeof head);
    
    cin >> n >> m;
    for(int i = 1; i <= m; i ++) {
        int u, v, w;
        scanf("%d %d %d", &u, &v, &w);
        add(u, v, w);
        add(v, u, w); // 无向图
    }
    
    cout << dijkstra() << endl;
    
    return 0;
}

以上是用优先队列实现，也可以用手写堆实现

• 手写堆的时间复杂度是${O(mlog(n))}$

• 优先队列的时间复杂度是${O(mlog(m))}$[但是m和n是基本上同一个数量级，所以没关系]

  为什么是优先队列是${O(mlog(m))}$？

   >if (dis[v] > du + edge[i].w) {
  // 每当距离变小则入堆，因此最坏情况是递减的
    dis[v] = du + edge[i].w;
    heap.push({dis[v], v});
   >}

练习eg:

AcWing-850.Dijkstra求最短路 II

AcWing-4871.最早时刻 添加条件约束的dijstra

AcWing-1488.最短距离 多源dijstra问题，建立超级源点，转换成单源，有点像多源BFS和差分约束

---

存在边权是负数

图中如果有负边权，一般都是用$SPFA$，什么年代了还在$Bellman-Ford$。

Bellman-Ford(${O(mn)}$))

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

struct Edge{
    int to;
    int w;
    int nxt;
};

const int N = 500 + 7;
const int M = 10000 + 7;

// 图
int head[N];
Edge edge[M]; int idx;
// 最短路
int dist[N];
int backup[N];  // dist[]备份

int n, m, k;

inline void add(int from, int to, int w) {
    edge[idx].to = to;
    edge[idx].w = w;
    edge[idx].nxt = head[from];
    head[from] = idx ++;
}

int Bellman_Ford(int k) {
    // 初始化距离
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;
     
    for (int e = 0; e < k; e ++) {
        // 备份
        memcpy(backup, dist, sizeof dist);
        // 遍历图中所有边
        for (int t = 1; t <= n; t ++) {
            for (int i = head[t]; i != -1; i = edge[i].nxt) {
                int j = edge[i].to;
                // 使用backup[]更新,而不是使用dist[]
                dist[j] = min(dist[j], backup[t] + edge[i].w);
            }
        }
    }
       
    // 存在负权边
    if (dist[n] > 0x3f3f3f3f / 2) return -1;
    
    return dist[n];
}


int main() {
    memset (head, -1, sizeof head);
    
    cin >> n >> m >> k;
    
    while (m --){
        int u, v, w;
        scanf("%d%d%d", &u, &v, &w);
        add(u, v, w);
    }
    
    int res = Bellman_Ford(k);
    
    if (dist[n] > 0x3f3f3f3f / 2) puts("impossible");
    else cout << res << endl;
    
    return 0;
}

练习eg:

AcWing853. 有边数限制的最短路

SPFA(${O(m) \sim O(mn)}$))

$SPFA$求最短路问题，需要记录额外两个变量:

int dis[N];        // 当前节点到源点的最短路径距离
bool inque[N];     // 当前节点是否在队列中，防止队列中同时存在重复的点

代码逻辑很像$Dijkstra$，但是是队列优化版的$Bellman-Ford$，
时间复杂度：最好$O(m)$，最坏$O(mn)$，取决于每个点的入队次数（$1 \sim n$次, $\gt n$次说明图中有负环）。

$SPFA$不但可以用来求最短路，还可以用来判断图中有无负环。

SPFA求最短路

特意把$Dijkstra$的部分做成了注释，方便对比：

#include <queue>
#include <iostream>
#include <cstring>

using namespace std;

typedef pair<int, int> PII;

const int N = 1e5 + 7;
const int M = 1e6 + 7;
const int INF = 0x3f3f3f3f;

struct Edge {
    int to;
    int w;
    int nxt;
};

Edge edge[M];
int head[N], idx = 1;
int dis[N]; bool inque[N]; //vis[N];  

int n, m;

inline void add(int from, int to, int w) {
    edge[idx].to = to, edge[idx].w = w, edge[idx].nxt = head[from];
    head[from] = idx ++;
}

int spfa() {
    memset(dis, 0x3f, sizeof dis);
    // memset(vis, 0, sizeof vis);
    dis[1] = 0;
    
    // priority_queue<PII, vector<PII>, greater<PII>> pq;
    // pq.push({0, 1});
    queue<int> q;
    q.push(1);    
    
    while(!q.empty()) {
        // int u = pq.top().second; pq.pop();
        int u = q.front(); q.pop();
        
        // if (vis[u]) continue;
        // vis[u] = true;
        inque[u] = false;
        
        int du = dis[u];
        
        for(int i = head[u]; ~i; i = edge[i].nxt) {
            int v = edge[i].to, w = edge[i].w;
            if (dis[v] > du + w) {
                dis[v] = du + w;
                // pq.push({dis[v], v})
                if (!inque[v]) inque[v] = true, q.push(v);
            }
        }
    }
    
    return dis[n];
}

int main() {
    memset(head, -1, sizeof head);

    cin >> n >> m;
    for(int i = 1; i <= m; i ++) {
        int u, v, w;
        scanf("%d %d %d", &u, &v, &w);
        add(u, v, w);
    }
    
    spfa();
    
    if (dis[n] == 0x3f3f3f3f) puts("impossible");
    else cout << dis[n] << endl;
    
    return 0;
}

SPFA判断负环

#include <queue>
#include <iostream>
#include <cstring>

using namespace std;

const int N = 2000 + 7;
const int M = 10000 + 7;

struct Edge {
    int to;
    int w;
    int nxt;
};

Edge edge[M];
int head[N], idx = 1;
// 最短路
int dis[N]; bool inque[N]; // 存的是当前该点是否在队列当中，防止队列中同时存在重复的点
// 判负环
int cnt[N];                // cnt[]记录dis[]更新次数

int n, m;

inline void add(int from, int to, int w) {
    edge[idx].to = to, edge[idx].w = w, edge[idx].nxt = head[from];
    head[from] = idx ++;
}

bool spfa() {
    memset(dis, 0x3f, sizeof dis);
    dis[1] = 0;
    
    queue<int> q;
    // q.push(1);
    // inque[1] = true;
    // 可能这个负环从源点1是到不了的，因此初始时要把所有点都放进que
    for (int i = 1; i <= n; i ++) {
        q.push(i);
        inque[i] = true;
    }
    
    while (!q.empty()) {
        int u = q.front(); q.pop();
        
        inque[u] = false;
        
        for (int i = head[u]; ~i; i = edge[i].nxt) {
            int v = edge[i].to, w = edge[i].w;
            if (dis[v] > dis[u] + w) {
                dis[v] = dis[u] + w;
                cnt[v] = cnt[u] + 1;
                // dis[]更新次数 >= n，说明存在负环
                if (cnt[v] >= n) return true;
                if (!inque[v]) inque[v] = true, q.push(v); 
            }
        }
    }
    
    return false;
}

int main() {
    memset(head, -1, sizeof head);
    
    cin >> n >> m;
    for(int i = 1; i <= m; i ++) {
        int u, v, w;
        scanf("%d %d %d", &u, &v, &w);
        add(u, v, w);
    }
    
    if(spfa()) puts("Yes");
    else puts("No");
    
    return 0;
}

练习eg:

Acwing-851. spfa求最短路

Acwing-852. spfa判断负环

---

多源最短路

Floyd(${O(n^3)}$))

Floyd算法本质上是一个动态规划的思想，每一次循环更新经过前k个节点，i到j的最短路径。

dist[k, i , j ]表示从点i开始，只经过1~k这些中间点，到点j的最短距离

这甚至不需要特意存图，因为dist数组本身就可以从邻接矩阵拓展而来。初始化的时候，我们把每个点到自己的距离设为0，每新增一条边，就把从这条边的起点到终点的距离设为此边的边权（类似于邻接矩阵）。其他距离初始化为INF（一个超过边权数据范围的大整数，注意防止溢出）。

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 200 + 7;
const int M = 20000 + 7;
const int INF = 0x3f3f3f3f;

int dist[N][N];

int n, m;
int Q; // Q表示询问次数

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

int main() {
    cin >> n >> m >> Q;
    // 邻接矩阵初始化
    for (int i = 1; i <= n; i ++) {
        for (int j = 1; j <= n; j ++) {
            if(i == j) dist[i][j] = 0;
            else dist[i][j] = INF;
        }
    }
    
    for(int i = 1; i <= m; i ++) {
        int u, v, w;
        scanf("%d%d%d", &u, &v, &w);
        // 通常只保留最短边
        dist[u][v] = min (dist[u][v], w);
    } 
    
    floyd();
    
    while (Q --) {
        int a, b;
        scanf("%d%d", &a, &b);
        if (dist[a][b] > INF / 2) puts("impossible");
        else printf("%d\n", dist[a][b]);
    }
    
    return 0;
}

练习eg:

AcWing854.Floyd求最短路