最短路

最短路

• 单元最短路
  • 边权都是正数
    • 朴素的Dijkstra -> O(n ^ 2)
    • heap + Dikstra -> O(m * logm)
  • 边权都是负数
    • Bellman-Ford -> O(nm)
    • SPFA 一般O(m)，最坏的情况O(nm)
• 多元最短路
  • 多源汇最短路 Floyed -> O(n ^ 3)

朴素Dijkstra

思路

每一次去集合外查找距离当前点最短的点

初始化

首先我们应该初始化dis数组，使dis[1] = 0，其余的点都是正无穷

memset(dist, 0x3f, sizeof dist);
dist[1] = 0;

接着我们去遍历s集合外还没有确定好最合适位置的点，判断谁是最小点

int t = -1;
for (int j = 1; j <= n; j ++ )
    if (!st[j] && (t == -1 || dist[t] > dist[j]))
        t = j;

接着对所有点点距离按照这一个点进行更新操作，将这个最小点放入到s集合当中

for (int j = 1; j <= n; j ++ )
dist[j] = min(dist[j], dist[t] + g[t][j]);
st[t] = true;

最后判断d[n]是否有数，如果为正无穷的话，说明不管以前面那一个点为最小点都无法到达这一个点，返回-1

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

完整代码

#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);
    //从1 -> 1距离为0
    dist[1] = 0;
    //遍历n - 1次
    for (int i = 0; i < n - 1; i ++ )
    {
        //t用来记录集合外距离原点最近的点
        int t = -1;
        //遍历所有结点
        for (int j = 1; j <= n; j ++ )
            //如果j并没有确定是最短路，并且发现j距离原点的距离更近的话，进行更新操作
            if (!st[j] && (t == -1 || dist[t] > dist[j]))
                t = j;
        
        //重新遍历一下所有结点，在原有点和走中转点之间取最小值
        for (int j = 1; j <= n; j ++ )
            dist[j] = min(dist[j], dist[t] + g[t][j]);

        //将已确定的最小点放入到st状态数组中
        st[t] = true;
    }
    //通过如下遍历，我们会发现st[n]的值为0，说明我
    // for(int i = 1;i <= n;i++) {
    //     cout << st[i] << " ";
    // }

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

int main()
{
    //输入有n个点，m个边
    cin >> n >> m;
    //初始化g数组为0x3f3f3f3f
    memset(g, 0x3f, sizeof g);
    while (m -- )
    {
        int a, b, c;
        //输入两边以及对应的权值
        cin >> a >> b >> c;
        //如果发现重边我们应该取最小值
        //本题要求我们计算从1 -> n点的最小路径
        g[a][b] = min(g[a][b], c);
    }

    //dijistra

    cout << dijkstra() << endl;

    return 0;
}

堆优化Dijstra

如果数据量假如很大，朴素版Dijstra两层for循环很容易爆炸

所以我们需要进行优化，那么使用什么进行优化呢？

在这里我们使用堆来进行优化

为什么我们要使用堆来优化？

Dijstra计算最短路径总共分为三步

• 记录最短路的状态 -> 外层for循环执行n次
• 每一次使用t来更新到达每一个条边m次
• 寻找最短边 -> O(n ^ 2)

很显然时间都卡在了最后寻找最短边身上了，寻找最小值，我们前面讲过小顶堆的特性，我们其实是可以使用heap进行存储

而堆存储时间复杂度是O(1)，修改堆中的某一个元素为O(log n)

三步中时间复杂度最多的也就是修改边这一步，即mlog(n)

初始化

存储元素需要改成邻接表存储

ne，e，h数组，idx记录每一个点的编号

创建优先队列( = 堆)

priority_queue<PII, vector<PII>, greater<PII>> heap;

堆中存储的元素类型为pair类型，第一位用来存储距离，第二位用来存储编号

add函数

相比于原理，我们需要为每一条边添加权值，即为每一个为每一个起点的编号作为下标添加权值

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

Dijstra函数

int dijkstra()
{
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;
    priority_queue<PII, vector<PII>, greater<PII>> heap;
  	//距离1号点的距离为0
    heap.push({0, 1});

    while (heap.size())
    {
     		//弹出集合外最短点
        auto t = heap.top();
        heap.pop();

        int ver = t.second, distance = t.first;
				//判断最短点是否早就被确定
        if (st[ver]) continue;
        st[ver] = true;
				//计算其余可到达点距离
        for (int i = h[ver]; i != -1; i = ne[i])
        {
            int j = e[i];
            if (dist[j] > dist[ver] + w[i])
            {
                dist[j] = dist[ver] + w[i];
                heap.push({dist[j], j});
            }
        }
    }

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

完整代码

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

using namespace std;

typedef pair<int, int> PII;

const int N = 1e6 + 10;

int n, m;
int h[N], w[N], e[N], ne[N], idx;
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>> heap;
    heap.push({0, 1});

    while (heap.size())
    {
        auto t = heap.top();
        heap.pop();

        int ver = t.second, distance = t.first;

        if (st[ver]) continue;
        st[ver] = true;

        for (int i = h[ver]; i != -1; i = ne[i])
        {
            int j = e[i];
            if (dist[j] > dist[ver] + w[i])
            {
                dist[j] = dist[ver] + w[i];
                heap.push({dist[j], j});
            }
        }
    }

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

int main()
{
    scanf("%d%d", &n, &m);

    memset(h, -1, sizeof h);
    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

可以用来解决边权为负数，可能出现负环或者是重边的情况

原理

Bellman_ford算法和宽搜很相似

我们需要备份上一次的状态，通过这个状态来更新下一次的值，保证每一次迭代就走了一步

简易模版

for 循环遍历n次
	for循环遍历所有边
		dis[b] = min(dis[b],dis[a] + w);

所有边都满足dis[b] <= dis[a] + w

初始化

所有我们可以使用邻接表或者是结构体进行存储

推荐使用结构体

struct Edge{
		int a,b,c; //a -> b 边权为c
}

注意

在我们使用bellman_ford算法计算最短路的时候，需要memcpy拷贝上一次的状态

通过这个状态对每一个点的dist进行更新操作

AC代码

#include <bits/stdc++.h>
using namespace std;
const int N = 100010;
struct Edge{
    int a,b,c;
}edges[N];
int n,m,k;
int d[N],bk[N];
int bellman_ford() {
    memset(d,0x3f,sizeof(d));
    d[1] = 0;
    for(int i = 0;i < k;i++) {
        memcpy(bk,d,sizeof(d));
        for(int j = 0;j < n;j++) {
            auto t = edges[j];
            d[t.b] = bk[t.a] + t.c; 
        }
    }

    if(d[n] > 0x3f3f3f3f / 2) return -1;
    return d[n];
}

int main(){
    cin >> n >> m >> k;
    for(int i = 0;i < n;i++) {
        int a,b,c;
        cin >> a >> b >> c;
        edges[i] = {a,b,c};
    }

    int t = bellman_ford();

    if(t == -1) cout << "impossible" << endl;
    else cout << t << endl;
    return 0;
}

SPFA

SPFA算法在求最短路领域使用的非常频繁，可以处理所有正负权值的情况，所以学会SPFA是必不可少的

SPFA算法主要是对Bellman_ford的一种优化算法，Bellman_ford每一次都保留每一次的状态，对下一个状态进行更新，而SPFA将Bellman_ford以宽搜队列的形式进行展现

实现SPFA类似Dijsktra，我们需要定义一个队列，从起始位置开始，通过邻接表不停的向下进行下去，直到遍历到根结点，此时不再向队列中添加元素，推出while循环

添加结点的方式相同，都是使用邻接表进行添加

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

SPFA核心算法

void spfa() {
		memset(d,0x3f,sizeof(d));
		d[1] = 0;
		st[1] = 1;
		queue<int> q;
    q.push(1);
    while(q.size()) {
    		int fr = q.front();
    		q.pop();
    		st[fr] = 0;
    		for(int i = h[fr];i != -1;i = ne[i]) {
    				int j = e[i];
    				if(d[j] > d[fr] + w[i]) {
    						d[j] = d[fr] + w[i];
    						if(!st[j]) {
    								q.push(j);
    								st[j] = 1;
    						}
    				}
    		}
    }
    
    return d[n];
}

初始化

d数组是用来记录该点到达原点的距离

memset(d,0x3f,sizeof(d));
d[1] = 0;

队列用来宽度优先遍历图

queue<int> q;
q.push(1); //添加遍历起点

st数组用来标记这个点是否在队列中

q.push(1);

宽度优先遍历

while(q.size()) {
    		int fr = q.front(); 
    		q.pop();
  			//st[fr] = 0代表fr这个点已经出队列了
    		st[fr] = 0;
  			//从这个点遍历所有他可以到达的点
    		for(int i = h[fr];i != -1;i = ne[i]) {
    				int j = e[i]; //拿出到达点的编号
    				if(d[j] > d[fr] + w[i]) {
              	//如果从1 -> j距离大于1 -> fr + fr -> i距离
    						d[j] = d[fr] + w[i]; //更新
              	cnt[j] = cnt[fr] + 1; //可以用来记录边的数量
    						if(!st[j]) { //如果队列里面有，不用重复加入队列，否则队列里面有两个相同的结点不执行一个点多次了嘛
    								q.push(j);
    								st[j] = 1;
    						}
    				}
    		}
    }

    return d[n]; //从1->n的最短路径
}

Floyed

Floyed算法使用来处理多源最短路问题的一种方法

Floyed算法总共需要三个参数，起点终点还有中转点

假设起点是st，终点是ed，中转点是k

我们想要计算g[st][ed]的值，我们其实可以转化成g[st][ed] = g[st][k] + g[k][ed]来计算距离

对两个表达式取最小值g[st][ed] = min(g[st][ed],g[st][k] + g[k][ed])

想要结果正确初始化也很重要

我们将g[i][i]初始化为0，其余的情况都初始化为INF，代表无法到达

假设两个点通过中转点并不能到达，那么最终结果一定是大于INF / 2的

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

AC代码

#include <bits/stdc++.h>
using namespace std;
#define INF 1e9
const int N = 210;
int n,m,k;
int g[N][N];

void floyed() {
    for(int k = 1;k <= n;k++) {
        for(int i = 1;i <= n;i++)  {
            for(int j = 1;j <= n;j++) {
                g[i][j] = min(g[i][j],g[i][k] + g[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) g[i][j] = 0;
            else g[i][j] = INF;
        }
    }
    while(m--) {
        int a,b,c;
        cin >> a >> b >> c;
        g[a][b] = min(g[a][b],c);
    }

    floyed();

    while(k--) {
        int a,b;
        cin >> a >> b;
        int t = g[a][b];
        if(t > INF / 2) cout << "impossible" << endl;
        else cout << t << endl;
    }

    return 0;
}