一、 最短路知识框架

最短路分两类题目

1.单源最短路

1.1 所有边权都是正数的最短路问题

1.1.1 稠密图用朴素的 Dijkstra算法

Step1: 初始化 dst[i] = 0x3f3f3f3f, dst[1] = 0
Step2: n次迭代，每轮迭代确定一个新的节点到起始点（也就是节点1）的最短距离
找出一个不在 s(已经确定最短距离的节点)中距离最近的节点 t
把 t加入到 s中
用 t更新其他所有到起始点的距离

代码模板

时间复杂度O(n^2)

int g[N][N];
int dst[N]; //当前所有节点到起始点的距离
int vst[N]; //当前已经计算出离起始点距离最近点的集合
int n, m;

int Dijkstra()
{
    memset(dst, 0x3f, sizeof dst);
    dst[1] = 0;

    for(int i = 1; i <= n; i++)
    {
        int t = -1;
        for(int j = 1; j <= n; j++)
        {
            if(vst[j] == false && (t == -1 || dst[j] < dst[t]))
            {
                t = j;
            }
        }

        vst[t] = true;
        for(int i = 1; i <= n; i++)
        {
            dst[i] = min(dst[i], dst[t] + g[t][i]);
        }
    }

    if(dst[n] == 0x3f3f3f3f) return -1; // 如何判断节点n到起始点没有路径
    else return dst[n];
}

1.1.2 稀疏图用堆优化版本的 Dijkstra算法

Step1: 初始化 dst[i] = 0x3f3f3f3f, dst[1]=0, 把q.push({0, 1})
Step2: 堆优化版本的dijkstra, 每次从堆中找出一个不在 s(已经确定最短距离的节点)中距离最近的节点 t，用小根堆取最小值
把 t加入到 s中
用 t更新其他所有到起始点的距离

代码模板

时间复杂度O(mlogn)

typedef pair<int, int> PII;

const int N = 100010, M = 100010;
int n, m;
int h[N], w[N], e[N], ne[N], idx;
int dst[N];
int 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(dst, 0x3f, sizeof dst);
    dst[1] = 0;

    priority_queue<PII, vector<PII>, greater<PII>> q;
    q.push({0, 1});
    //st[1] = true;

    while(q.size())
    {
        PII head = q.top();
        q.pop();

        int t = head.second, distance = head.first;
        if(st[t]) continue;
        st[t] = true;
        //cout << endl << "cur minist node=" << t << endl;

        for(int i = h[t]; i != -1; i = ne[i])
        {
            int j = e[i];
            if(dst[j] > distance + w[i]) //w[i]存储的是从i到i的next节点的边长，这里已经犯过两次错误！！！！！！
            {
                dst[j] = distance + w[i];
                q.push({dst[j], j});
            }
            //cout << t << "-->" << j << ", distance=" << dst[j] << " ";
        }

    }

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

1.2 存在边权为负数的最短路问题

1.2.1 bellman_ford算法

Step1: 初始化 dst[i] = 0x3f3f3f3f, dst[1] = 0
Step2: n次迭代，每次迭代更新所有边 dst[b] = min(dst[b], backup[a] + w)

知识点：n次迭代有物理意义：从起点1开始不超过k条边，所有节点到起点的最短路距离
注意点：
（1）备份dst数组，更新用 backup数组更新
（2）判断无最短路径条件和 dijkstra算法的区别，这里虽然也是无穷大，但可能会更新dst[n]

const int N = 510, M = 100010;

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

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

int bellman_ford()
{
    memset(dst, 0x3f, sizeof dst);
    dst[1] = 0;

    for(int i = 1; i <= k; i++)
    {
        memcpy(backup, dst, sizeof dst);
        for(int j = 0; j <= m - 1; j++)
        {
            int a = edges[j].a, b = edges[j].b, w = edges[j].w;
            dst[b] = min(dst[b], backup[a] + w); // 注意，这里用backup更新
        }
    }

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

1.2.2 spfa算法

核心思想：改进bellman_ford算法，用一个队列保存所有距离有更新（变小）的节点（因为最短距离有变小的节点后继节点才会进一步变小）
step1: 初始化 dst[i] = 0x3f3f3f3f, dst[1] = 0, q.push(1)
step2:
while q不空
从队列头取出元素t，删除对头元素
vst[t] = false
更新所有t的出边，如果有更新，则把更新后的节点加入队列当中

代码模板

时间复杂度：一般O(m), 最坏情况下O(om)

int spfa()
{
    memset(dst, 0x3f, sizeof dst);
    dst[1] = 0;

    queue<int> q;
    q.push(1);

    while(q.size())
    {
        int t = q.front();
        q.pop();

        vst[t] = false;
        for(int i = h[t]; i != -1; i = ne[i])
        {
            int j = e[i];
            if(dst[j] > dst[t] + w[i])
            {
                dst[j] = dst[t] + w[i];
                if(vst[j] == false)
                {
                    vst[j] = true;
                    q.push(j);
                }
            }
        }
    }

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

spfa 是否存在环的代码

int spfa()
{
    queue<int> q;
    for(int i = 1; i <= n; i++)
    {
        q.push(i);
        st[i] = true;
    }

    while(q.size())
    {
        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] == false) {
                    q.push(j);
                }
            }
        }
    }

    return false;
}

(2) 多源最短路

时间复杂度O(n^3)

int dst[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++)
            {
                dst[i][j] = min(dst[i][j], dst[i][k] + dst[k][j]);
            }
        }
    }
}