最短路问题

五种最短路的解决方法

1、Dijkstra算法：

时间复杂度：

​ 朴素版 O(n^2)，用于无负权边

核心思路：

​ 每次找到集合中距离最短的边进行更新，并用这条确定的最短的边去扩展与他相连通的所有点，
​ 并更新距离，用st[]数组标记已经找到了最短距离。
​ 稀疏图用邻接矩阵存，反之用邻接表存。

注意：

​ （1）邻接矩阵存边时，可以用g[a][b] = min(g[a][b], c)，避免重边和自环，但也要先初始化memset(g,0x3f, sizeof g);

代码模板：

int dijkstra()
{
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;    //第一个的点到起点的距离为0

    for (int i = 1; i <= n; i ++)    //迭代n次，有n个点需要找到最短距离，每次迭代找一个最短距离
    {
        int t = -1;
        for (int j = 1; j <= n; 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[t] = true;
    }
    if (dist[n] == 0x3f3f3f3f) return -1;
    return dist[n];
}

2、堆优化版Dijkstra算法：

时间复杂度：

​ O(mlogn)，用于无负权边。

核心思路：

​ 对朴素版 Dijkstra算法的核心进行优化，就是每次取出的是所有边中最短的边，
​ 我们可以利用小根堆去维护需要遍历的所有边，这样每次取出堆顶元素，即最短的边了。

注意：

​ （1）pair类型的优先队列是按照第一个关键词进行排序的，故第一位只能放距离。
​ （2）邻接表初始化表头memset(h, -1, sizeof h);
​ （3）初始化距离数组dist为 INF，便于寻找最短路径。

代码模板：

int dijkstra() 
{
    memset(dist, 0x3f, sizeof dist);    //初始化起点到所有的点的距离为无穷大
    dist[1] = 0;    //初始化第一个点到起点的距离为0
    priority_queue<PII, vector<PII>, greater<PII>> heap;    //创建一个PII类型的优先队列，小根堆
    heap.push({0, 1});  //将起点1，距离起点距离0，放入堆中

    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])    //对邻接表进行遍历，这里遍历的是h[ver]是ver为表头的邻接表的元素
        {
            int j = e[i];   //存下当前点的值
            if (dist[j] > dist[ver] + w[i]) //如果当前的点到起点的距离小于原有距离（初始值或之前本次遍历时获得的值）
            {
                dist[j] = dist[ver] + w[i]; //更新dist最短距离的值
                heap.push({dist[j], j});    //将该点的距离和位置放入堆中
            }
        }
    }

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

3、Bellman-ford算法：

时间复杂度：

​ O(nm)，用于有数限制的最短路问题。
​ 与其他最短路算法不同是，Bellman-ford算法需要自己定义一个结构体，进行存边。

核心思路：

​ （1）初始化dist数组，并初始化起点的距离
​ （2）迭代k次，表示只能经过k条边
​ （3）迭代所有边，即迭代m次，每次迭代前备份一下上一次的dist数组(last)，用于后续更新dist距离，
​ （4）第m次时迭代更新与起点距离m条边及以内的点的最短距离（松弛）

注意：

​ （1）if (dist[n] > 0x3f3f3f3f / 2) return 0，因为存在负权边。
​ （2）每次都遍历会遍历所有边，有很多边是无效的，spfa算法针对这一点进行优化。

代码模板：

int bellman_ford()
{
    memset(dist, 0x3f, sizeof dist);        //初始化所有的点到起点的距离都是无穷大

    dist[1] = 0;    //初始化第一个点到起点的距离为0

    for (int i = 0; i < k; i ++)    //遍历k次， 表示经过k条边
    {
        memcpy(last, dist, sizeof dist);    //每次遍历备份一下上一次遍历结果的数组，因为可能在更新的时候，会改变dist，导致后续在更新时值不丢
        for (int j = 0; j < m; j ++)   //有m个边需要去遍历,每次求出一条件的路径
        {
            auto e = edges[j];  //将每一行的数据值（c）和方向（a->b）取出
            dist[e.b] = min(dist[e.b], last[e.a] + e.c);    //每次取出直接到达该点的距离和原有距离的最小值
        }
    }

    if (dist[n] > 0x3f3f3f3f / 2) return 0;
    return dist[n];
}

4、Spfa算法：

时间复杂度：

​ O(m) 是对bellman_ford算法中松弛一步的优化。 不能含有负权回路。

思路：

​ （1）初始化dist数组
​ （2）定义一个循环队列，将需要更新最短距离的点加入队列中，这样就不用每次去寻找需要更新的边了
​ （3）遍历队列中的元素，只要该元素所在的连通块中，存在新的最短距离，就将其加入队列中，去更新后面的元素距离。

注意：

（1）这里的st[]数组意义和Dijkstra算法不同，
Dijkstra算法中st[]数组表示是否求出最短距离；
Spfa算法中st[]数组表示某个点是否在队列中。
（2）Spfa算法能求含负权边的原因，也是因为（1）中的特性，若存在负权边，就会去重新更新与该点连接的边的最短距离。
（3）Spfa最坏情况是O(nm)
（4）循环队列写法：

​ hh = 0, tt = 0, q[tt ++] = 1;
​ while (hh != tt);
​ int t = q[hh++];
​ if (tt == N) tt = 0;
​ …
​ q[tt ++] = x;
​ if (tt == N) tt = 0;

​ (5)spfa算法最后判断的条件是dist[n] == INF的原因是，bellman_ford算法会遍历所有的边，因此不管是不是和源点连通的边它都会得到更新；但spfa算法不一样，他相当于采用BFS，因此遍历到的结点都是与源点连通的，因此如果你要求的n和源点不连通，它不会得到更新，还是保持的0x3f3f3f3f。

代码模板：

int spfa()
{
    memset(dist, 0x3f, sizeof dist);    //初始化最初距离为无穷
    dist[1] = 0;    //初始化第一个点到起点的距离

    queue<int> q;   //定义一个队列用于存放待更新的值
    q.push(1);  //将起点放进去
    st[1] = 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];       //更新距离
                if (!st[j])                     //如果这个点不在队列中，
                {
                    q.push(j);  //就将其加入队列中，并进行标记
                    st[j] = true;
                }
            }
        }
    }

    return dist[n];


}

5、spfa算法判负环：

时间复杂度：

​ O(m)

核心思想：

若图中存在负环，那么spfa算法就会一直不断地更新最短距离，故只要我们发现更新次数 >= n次，
就说明有负环，因为n个点只需要n - 1条边连接，故只需要更新n - 1次。
故我们只需要在每次更新最短距离时，更新cnt[j] = cnt[t] + 1即可，最后若更新次数 >= n次，就结束循环，返回true。
注意：
（1）这里需要注意，可能负环与起点1，不连通，故需要将所有点都加入到队列中，然后开始spfa算法遍历即可。

代码模板：

int spfa()
{
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;
    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[t] > n) return true;    //如果更新次数大于n，说明至少走过了n + 1个点，说明存在循环，即负权回路
                if (!st[j])
                {
                    q.push(j);
                    st[j] = true;
                }
            }
        }
    }
    return false;
}

6、Floyd算法：

时间复杂度：

​ O(n^3) 多源最短路问题。

核心思路：

基于DP：
（1）状态表示：f[k][i][j]
所有从i出发，最终走到j，且中间只经过节点编号不超过k的所有路径。
（2）属性：min
（3）状态计算：
以第i个点是否在路径中进行划分：
所有不包含节点k的路径：d[k - 1][i][j]
所有包含节点k的路径：d[k - 1][i][k] + d[k - 1][k][j]
（4）由于每次用的都是上一层的d，故可以把k层优化掉
即 d[i][j] = min(d[i][j], d[i][k] + d[k][j])

注意：

（1）初始化：自环设置成d[i][j] = 0，其他情况设置成INF，便于求min
（2）用邻接矩阵存边，直接d[a][b] = min(d[a][b], c);

代码模板：

初始化：
（1）i != j，d[i][j] = 0x3f3f3f3f，无穷，便于后续求最短路
（2）i == j，d[i][j] = 0，自环
实现：
    for (int k = 1; k <= n; k ++ )
        for (int i = 1; i <= n; i ++ )
            for (int j = 1; j <= n; j ++ )
//i到j的最小距离距离=原有距离与上一个点的距离到起点的距离+上一点到当前点的距离的最小值
                d[i][j] = min(d[i][j], d[i][k] + d[k][j]);