单元最短路

1. Dijkstra(heap)
2. SPFA

全源最短路

3. Floyd
4. Johnson

1. Dijkstra(heap)

堆优化版本的Dijkstra
时间复杂度 O((n+m)logn)
m表示边 n表示点
m次入堆 n次出堆
堆中存的是点

只能求解非负权图
一条负权值边都不能有

思路如下
算法根据点展开
节点分成两个集合
S:已经确定最短长度的点集
T:尚未确定最短长度的点集

#include<cstring>//memset函数的头文件
#include<iostream>
#include<algorithm>
#include<queue>
#define x first 
#define y second
using namespace std;
const int N = 150010;
typedef pair<int, int>PII;//前者是距离 堆中按照前者距离排序 后者是点序号
priority_queue<PII, vector<PII>, greater<PII>>heap;//小根堆
int h[N], w[N], e[N], ne[N], idx;//稀疏图用邻接表储存 w[N]存权重
int dist[N];//起点点到终点的(当前)最短距离
bool vis[N];//标记起点到某个点的最短距离是否确定
int st,ed;//起点到终点
int n, m;

//数组模拟邻接表的插入函数
void add(int a, int b, int c)//存在一条从点a到点b的有向边 距离为c
{
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx++;
}

int Dijkstra(int st, int ed)
{
    //初始设定起点点到其他所有点距离为正无穷
    memset(dist, 0x3f, sizeof dist);

    //起点到起点距离为0 加入堆
    dist[st] = 0;
    //第一参数是距离
    //第二参数是终点编号
    heap.push({ 0,st });

    while (heap.size())
    {
        auto t = heap.top();
        heap.pop();//取出后一定要弹出

        int ver = t.y, distance = t.x;//ver取得该点的下标

        if (vis[ver])continue;//已经确定了就跳过

        //要做就先确定下来
        //出队时确定加入S集合
        vis[ver] = true;

        //把确定下来的那个点能拓展到的新点 加入堆
        for (int i = h[ver];~i;i = ne[i])
        {
            int j = e[i];
            if (dist[j] > distance + w[i])
            {
                dist[j] = distance + w[i];
                heap.push({ dist[j],j });
            }
        }
    }

    if (dist[ed] == 0x3f3f3f3f)return -1;//不连通

    return dist[ed];
}

int main()
{
    memset(h, -1, sizeof h);//初始化邻接表表头

    scanf("%d%d", &n, &m);

    while (m--)
    {
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        add(a, b, c);
    }

    scanf("%d%d", &st, &ed);

    printf("%d\n", Dijkstra(st, ed));

    return 0;
}

2. SPFA

时间复杂度 O(mn)
SPFA算法是Bellman-Ford算法的队列优化
最坏的情况是 O(mn)
n轮SPFA经常TLE

SPFA可以分析有负权值的最短路
并且能对最短路不存在的情况进行判断

最短路不存在的两种情况
1. 有向图存在负环
2. 无向图存在负权边

#include<cstring>//memset函数的头文件
#include<iostream>
#include<algorithm>
#include<queue>
using namespace std;
const int N = 150010;
typedef pair<int, int>PII;//前者是距离 堆中按照前者距离排序 后者是点序号
int h[N], w[N], e[N], ne[N], idx;//稀疏图用邻接表储存 w[N]存权重
int dist[N];//起点点到终点的(当前)最短距离
bool vis[N];//标记i点是否在队列中(是否可能拓展更新领域点)
int cnt[N];//记录最短路径经过多少边
queue<int>q;
int st, ed;//起点和终点
int n, m;

void add(int a, int b, int c)//存在一条从点a到点b的有向边 距离为c
{
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx++;
}

int SPFA(int st, int ed)
{
    memset(dist, 0x3f, sizeof dist);

    dist[st] = 0;
    q.push(st);
    vis[st] = true;

    while (q.size())
    {
        int t = q.front();
        q.pop();
        vis[t] = false;

        //更新t的所有邻边 
        //t的所有邻边在头为t的链表上
        for (int i = h[t];~i;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;

                //n个点的最短路只需要n个点
                //如果更新超过n次
                //说明有重复更新
                //说明无最短路
                if (cnt[j] > n)return -1;

                //如果能更新 就要考虑是否需要重新入队
                //SPFA算法中一个点可能会多次入队
                if (!vis[j])
                {
                    q.push(j);
                    vis[j] = true;
                }
            }
        }
    }

    return dist[ed];
}

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

    scanf("%d%d", &st, &ed);

    printf("%d", SPFA(st, ed));

    return 0;
}

比较Dijkstra和SPFA

堆优化的Dijkstra和SPFA的区别是

前者每次取出可以拓展的最小边
从而确定一个点的最短路径
每一个点不会重复入堆

后者每次将所有可以拓展的点全部入队
进行松弛操作
每一个点可能重复入队

Dijkstra的vis数组:最短路径是否确定
SPFA的vis数组:是否在队列中

处理正权图优先考虑Dijkstra
处理负权图优先考虑SPFA

3. Floyd

时间复杂度 O(n^3)
Floyd算法求任意两点之间的最短路
可以处理带负权图
但最短路必须存在(不能有负环)
使用邻接矩阵存图
空间复杂度 O(n^2)
点的个数过多容易MLE

#include <iostream>
using namespace std;
const int N = 210, INF = 0x3f3f3f3f;
int n, m, k;
int x, y, z;
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;

    //初始化距离数组
    //自己到自己距离初始化为0
    //其余一律正无穷
    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--) 
    {
        cin >> x >> y >> z;

        d[x][y] = min(d[x][y], z);
        //注意保存最小的边(处理重边)
    }

    Floyd();

    while (k--) 
    {
        cin >> x >> y;

        //由于有负权边存在
        //INF可能被负权值更新 从而略微变小
        //但实际意义仍然是不可到达
        //所以用INF/2判断
        if (d[x][y] > INF / 2) puts("-1");
        else cout << d[x][y] << endl;
    }

    return 0;
}

Floyd算法
除了求最短路
还可以求最小权值的环
O(n^2)遍历求最小值

例如
D(1,2)=4
D(2,1)=2
则该环为6

还可以检验可达性
判断是否连通

    for (int k = 1; k <= n; k++)
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= n; j++)
                f[i][j] |= (f[i][k] & f[k][j]);

4. Johnson

时间复杂度 O(mn+mnlogm)
可以用邻接表存图
空间占用更小
能处理含有更多点的图

思路如下
1. 添加虚拟点 并添加指向所有节点的虚拟边 这些边的权重设为0
2. 以虚拟点为起点执行一次SPFA 求出到其他各点i的最短距离 这些最短距离存到h[i]
3. 用h[i]更新原来所有边的权值 e[u,v]+=h[u]-h[v]
4. 对于每一次询问执行Dijkstra

洛谷P5905

#include<bits/stdc++.h>
#define x first
#define y second
using namespace std;
const int N = 3e3 + 10, INF = 1e9;
typedef long long LL;
typedef pair<LL, LL> PII;
vector<PII> G[N];
LL h[N], dist[N];
int n, m, cnt[N];
bool vis[N];

//快读
int read()
{
    char ch = getchar();
    int f = 1;
    while (ch < '0' || ch>'9') { if (ch == '-') f = -f; ch = getchar(); }
    int k = 0;
    while (ch >= '0' && ch <= '9') k = (k << 3) + (k << 1) + ch - '0', ch = getchar();return k * f;
}

//从源点开始求一遍最短路 存入h数组
bool SPFA(int s) 
{   
    memset(h, 0x3f, sizeof(h));

    queue<int>q;

    h[s] = 0; 
    q.push(s);
    vis[s] = true; 

    while (!q.empty()) 
    {
        int u = q.front();
        q.pop(); 
        vis[u] = false;
        for (int i = 0;i < G[u].size();i++) 
        {
            int v = G[u][i].x, w = G[u][i].y;

            if (h[v] > h[u] + w) 
            {
                h[v] = h[u] + w;
                cnt[v] = cnt[u] + 1;

                //n是点数 最短路径最多n个点
                //达到n+1个点时一定有负环
                if (cnt[v] > n)return false;

                if (!vis[v])
                {
                    q.push(v);
                    vis[v] = true;
                }
            }
        }
    }

    return true;
}

void Dijkstra(int s) 
{   
    //每次Dijkstra是独立的 初始化vis数组
    memset(vis, 0, sizeof(vis));

    //每次Dijkstra的堆都是新的
    priority_queue<PII，vector<PII>,greater<PII>> q; //小根堆的使用

    //除了起点 其他点都设为正无穷
    for (int i = 1;i <= n;i++) dist[i] = (i == s) ? 0 : (INF);

    q.push({ 0,s });

    while (!q.empty()) 
    {
        int u = q.top().y;
        q.pop(); 

        if (vis[u]) continue;

        vis[u] = true; 

        for (int i = 0;i < G[u].size();i++) 
        {
            int v = G[u][i].x, w = G[u][i].y;
            if (dist[v] > dist[u] + w) 
            {
                dist[v] = dist[u] + w;
                if (!vis[v]) q.push({ dist[v], v });
            }
        }
    }
}

int main() 
{
    n = read(), m = read();

    while (m--) 
    {
        int u = read(), v = read(), w = read();
        G[u].push_back({ v,w });
    } 

    //构建虚拟点(超级源点)
    //该点到其他所有点的虚拟边设置权值为0
    for (int i = 1;i <= n;i++)G[0].push_back(make_pair(i, 0));

    //SPFA判断负环
    //有负环直接结束
    if (!SPFA(0)) { puts("-1");return 0; }

    //更新原来所有边的权值
    for (int u = 1;u <= n;u++)
        for (int i = 0;i < G[u].size();i++)
            G[u][i].y += h[u] - h[G[u][i].x];

    //对于每一次询问执行一次Dijkstra
    for (int i = 1;i <= n;i++) 
    {
        Dijkstra(i);

        LL ans = 0;
        for (LL j = 1;j <= n;j++)
            ans += (dist[j] == INF) ? (j * INF) : (j * (dist[j] + h[j] - h[i]));

        printf("%lld\n", ans);
    }

    return 0;
}