最短路

单源最短路

所有边权值非负

朴素Dijkstra 适合稠密图，用邻接矩阵
堆优化Dijkstra 适合稀疏图，用邻接表

存在负权边

Bellman-Ford 有边数限制的最短路问题
SPFA

多汇源最短路

Floyd

朴素Djikstra

思路:进行n次迭代确定每个点到起点的最小值
1.初始化距离
2.for(n个点）{//每次确定一个点到起点的最短路，并标记为st[i] = true;
int t = -1;
for(n个点){
//如果当前点没有被确定最短路
//如果当前点没有被更新过或发现新的最短路
更新t；
}
标记t
for(n个点){
用t点更新其它点到起点的距离
}
}

模板题 [Dijkstra求最短路]

给定一个 n 个点 m 条边的有向图，图中可能存在重边和自环，所有边权均为正值。

请你求出 1 号点到 n 号点的最短距离，如果无法从 1 号点走到 n 号点，则输出 −1。

输入格式
第一行包含整数 n 和 m。

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

输出格式
输出一个整数，表示 1 号点到 n 号点的最短距离。

如果路径不存在，则输出 −1。

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

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

    #include<bits/stdc++.h>

    using namespace std;

    const int N = 510;

    int n, m;
    int g[N][N];
    int dist[N];

    bool st[N];

    int Dijkstra()
    {
    	memset(dist, 0x3f, sizeof dist);
    	dist[1] = 0;
    	for( int i = 1; i <= n; i++ ){
    		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] = min(dist[j], g[t][j]+dist[t]);
    	}
    	if(dist[n]==0x3f3f3f3f)
    		return -1;
    	return dist[n];
    }

    int main()
    {
    	cin>>n>>m;
    	memset(g, 0x3f, sizeof g);
    	while(m--){
    		int x, y, z;
    		cin>>x>>y>>z;
    		g[x][y] = min(g[x][y], z);
    	}
    	cout<<Dijkstra()<<endl;
    	
    	return 0;
    }

堆优化的Dijkstra

思路：通过小根堆来维护当前未在st中出现且离远点最近的点
与朴素做法相比少了一个确定当前距离远点最近点t的for循环，时间复杂度O(mlogn)<O(n^2)

模板题【Djikstra求最短路】

给定一个 n 个点 m 条边的有向图，图中可能存在重边和自环，所有边权均为非负值。

请你求出 1 号点到 n 号点的最短距离，如果无法从 1 号点走到 n 号点，则输出 −1。

输入格式
第一行包含整数 n 和 m。

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

输出格式
输出一个整数，表示 1 号点到 n 号点的最短距离。

如果路径不存在，则输出 −1。

数据范围
1≤n,m≤1.5×105,
图中涉及边长均不小于 0，且不超过 10000。

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

代码：

    #include<cstdio>
    #include<iostream>
    #include<cstring>
    #include<algorithm>
    #include<queue>

    #define x first
    #define y second

    using namespace std;

    const int N = 1e6+10;

    typedef pair<int, int> PII;

    int n, m;
    int h[N], e[N], ne[N], idx, w[N];
    int dist[N];

    bool st[N];

    void add(int a, int b, int c)
    {
        e[idx] = b;
        w[idx] = c;
        ne[idx] = h[a];
        h[a] = idx++;
    }

    int Dijkstra()
    {
        memset(dist, 0x3f, sizeof dist);
        dist[1] = 0;
        priority_queue< PII, vector<PII>, greater<PII> > q;
        q.push({0, 1});
        while(q.size()){
            auto t = q.top();
            q.pop();
            int dis = t.x, ver = t.y;
            if(st[ver])
                continue;
            st[ver] = true;
            for( int i = h[ver]; i != -1; i = ne[i] ){
                int j = e[i];
                if(dist[j] > dis + w[i]){
                    dist[j] = dis + w[i];
                    q.push({dist[j], j});
                }
            }
        }
        if(dist[n]==0x3f3f3f3f)
            return -1;
        return dist[n];
    }

    int main()
    {
        memset(h, -1, sizeof h);
        dist[1] = 0;
        scanf("%d%d", &n, &m);
        while(m--){
            int a, b, c;
            scanf("%d%d%d", &a, &b, &c);
            add(a, b, c);
        }
        printf("%d\n", Dijkstra());
        
        return 0;
    }

Bellman_Ford算法

思路：
for(k次，经过不超过k条边到各点的最短路){
备份,只用上一次的结果
for(所有边，abw){
dist[b] = min(dist[b], backup[a]+w);//松弛操作，即缩短距离
}

模板题【有边数限制的最短路】

给定一个 n 个点 m 条边的有向图，图中可能存在重边和自环， 边权可能为负数。

请你求出从 1 号点到 n 号点的最多经过 k 条边的最短距离，如果无法从 1 号点走到 n 号点，输出 impossible。

注意：图中可能 存在负权回路 。

输入格式
第一行包含三个整数 n,m,k。

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

输出格式
输出一个整数，表示从 1 号点到 n 号点的最多经过 k 条边的最短距离。

如果不存在满足条件的路径，则输出 impossible。

数据范围
1≤n,k≤500,
1≤m≤10000,
任意边长的绝对值不超过 10000。

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

    #include<bits/stdc++.h>

    using namespace std;

    const int N = 510, M = 1e6+10, INF = 0x3f3f3f3f;

    int n, m, k;
    int dist[N], backup[N];

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

    int bellman_ford()
    {
        memset(dist, 0x3f, sizeof dist);
        dist[1] = 0;
        for( int i = 1; i <= k; i++ ){
            memcpy(backup, dist, sizeof dist);
            for( int j = 1; j <= m; j++ ){
                int a = edges[j].a, b = edges[j].b, w = edges[j].w;
                dist[b] = min(dist[b], backup[a]+w);
            }
        }
        return dist[n];
    }

    int main()
    {
        cin>>n>>m>>k;
        for( int i = 1; i <= m; i++ ){
            int a, b, w;
            cin>>a>>b>>w;
            edges[i] = {a, b, w};
        }
        int t = bellman_ford();
        if(t > INF/2)
            puts("impossible");
        else
            cout<<t<<endl;
        
        return 0;
    }

SPFA算法

思路：是bellman_ford的队列优化算法别称，对松弛操作做了优化。

模板题：【spfa求最短路】

给定一个 n 个点 m 条边的有向图，图中可能存在重边和自环， 边权可能为负数。

请你求出 1 号点到 n 号点的最短距离，如果无法从 1 号点走到 n 号点，则输出 impossible。

数据保证不存在负权回路。

输入格式
第一行包含整数 n 和 m。

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

输出格式
输出一个整数，表示 1 号点到 n 号点的最短距离。

如果路径不存在，则输出 impossible。

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

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

代码

      #include<bits/stdc++.h>

      #define x first
      #define y second

      using namespace std;

      const int N = 1e5+10;

      typedef pair<int, int> PII;

      int n, m;

      int h[N], e[N], ne[N], idx, w[N];
      int dist[N];

      bool st[N];

      void add(int a, int b, int c)
      {
      	e[idx] = b;
      	w[idx] = c;
      	ne[idx] = h[a];
      	h[a] = idx++;
      }

      int spfa()
      {
      	queue<PII> q;
      	memset(dist, 0x3f, sizeof dist);
      	dist[1] = 0;
      	q.push({0, 1});
      	st[1] = true;
      	while(!q.empty()){
      		auto t = q.front();
      		q.pop();
      		int p = t.y;
      		st[p] = false;
      		for( int i = h[p]; i != -1; i = ne[i] ){
      			int j = e[i];
      			if(dist[j] > dist[p]+w[i]){
      				dist[j] = dist[p]+w[i];
      				if(!st[j]){
      					st[j] = true;
      					q.push({dist[j], j});
      				}
      			}
      		}
      	}
      		return dist[n];
      }

      int main()
      {
      	cin>>n>>m;
      	memset(h, -1, sizeof h);
      	while(m--){
      		int a, b, c;
      		cin>>a>>b>>c;
      		add(a, b, c);
      	}
      	int res = spfa();
      	if(res==0x3f3f3f3f)
      		puts("impossible");
      	else
      		cout<<res<<endl;
      	
      	return 0;
      }

模板题：【spfa判断负环】

思路：
初始将所有点加入队列
while(队列非空){
取队头元素h并标记
遍历h点相连的点
若可以松弛操作，cnt【h】 = cnt[j]+1;
如果cnt超过n，说明有环
若j不在队列将其入队（没完全理解）
}

给定一个 n 个点 m 条边的有向图，图中可能存在重边和自环， 边权可能为负数。

请你判断图中是否存在负权回路。

输入格式
第一行包含整数 n 和 m。

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

输出格式
如果图中存在负权回路，则输出 Yes，否则输出 No。

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

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

    #include<bits/stdc++.h>

    using namespace std;

    const int N = 2010, M = 10010;

    int n, m;
    int h[N], e[M], ne[M], idx, w[M];
    int dist[N], cnt[N];

    bool st[N];

    void add(int a, int b, int c)
    {
    	e[idx] = b;
    	w[idx] = c;
    	ne[idx] = h[a];
    	h[a] = idx++;
    }

    bool spfa()
    {
    	queue<int> q;
    	for( int i = 1; i <= n; i++ ){
    		st[i] = true;
    		q.push(i);
    	}
    	while(!q.empty()){
    		int t = q.front();
    		q.pop();
    		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]){
    					st[j] = true;
    					q.push(j);
    				}
    			}
    		}
    	}
    	return false;
    }

    int main()
    {
    	cin>>n>>m;
    	memset(h, -1, sizeof h);
    	while(m--){
    		int a, b, c;
    		cin>>a>>b>>c;
    		add(a, b, c);
    	}
    	if(spfa())
    		puts("Yes");
    	else
    		puts("No");
    	
    	return 0;
    }

Floyd算法

思路：动态规划
f[i, j, k]代表从i到j路径上除i和j点外只经过i~k点的所有路径的最短距离
因此在计算k层f[i, j]必须把k-1层的所有状态计算出来，因此k放最外层
d[i, j] = min(d[i][j], d[i][k]+d[k][j]);

模板题：【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≤n2
1≤m≤20000,
图中涉及边长绝对值均不超过 10000。

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

    #include<bits/stdc++.h>

    using namespace std;

    const int N = 210, INF = 0x3f3f3f3f;

    int n, m, k;
    int d[N][N];

    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]);
    }

    int main()
    {
    	cin>>n>>m>>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;
    	while(m--){
    		int a, b, w;
    		cin>>a>>b>>w;
    		d[a][b] = min(d[a][b], w);
    	}
    	floyd();
    	while(k--){
    		int a, b;
    		cin>>a>>b;
    		if(d[a][b] > INF/2)
    			puts("impossible");
    		else
    			cout<<d[a][b]<<endl;
    	}
    	
    	return 0;
    }