最短路径算法

Floyd

原理

  使用邻接矩阵存储图更为合理，因为floyd算法要求每两个点之间的最短路径。循环顺序是kij其中k是阶段，从ik到kj点的最短路径由松弛操作

$$g[i][j] = min(g[i][j], g[i][k] + g[k][j])$$

给出。当有重边和自环时，每两个点之间存储的g[i][j]只存储最短的一条即可。时间复杂度为O(n^3)。

模板

void floyd()
{
    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]);
}

例题

AW.854 Floyd求最短路（简单）

Dijkstra

原理

  使用dist数组来维护所有点到源点的最短距离，用st数组维护已经确定最短距离的点。st数组一定要从空集开始，这样才能更新1号点。从所有点中选择距离源点最近的点来更新，将其所有临接点到源点的最短距离更新。最终更新了n个点后，所有点到达最短距离。时间复杂度为O(n^2)。

模板

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

using namespace std;

const int N = 510, INF = 0x3f3f3f3f;

int d[N][N];
int n, m;
int dist[N];
bool st[N];

void 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 ++ )
            if (dist[j] > dist[t] + d[t][j])
                dist[j] = dist[t] + d[t][j];
    }

    if (dist[n] == INF) cout << "-1" << endl;
    else cout << dist[n] << endl;
}

int main()
{
    cin >> n >> m;
    memset(d, 0x3f, sizeof d);

    for (int i = 1; i <= m; i ++ )
    {
        int a, b, c;
        cin >> a >> b >> c;
        d[a][b] = min(d[a][b], c);
    }

    dijkstra();

    return 0;
}

堆优化的Dijkstra

原理

  维护一个堆，堆中储存一对信息（距离源点距离，当前点序号），从而每次得到距离源点最近的点的编号，扩展所有邻接点。这里不能保证每个点只入堆一次，因此当第一次从堆出来以后，再出来的就是错误的更新点，因此使用判重布尔数组st来continue。时间复杂度因为有堆进行优化，所以是O(mlogn)。

模板

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

#define x first
#define y second

using namespace std;

typedef pair<int, int> PII;

const int N = 150010, INF = 0x3f3f3f3f;

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

void dijkstra()
{
    memset(dist, 0x3f, sizeof dist);
    priority_queue<PII, vector<PII>, greater<PII>> heap;

    dist[1] = 0;

    heap.push({0, 1});

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

        int ver = t.y, distance = t.x;

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

        for (int i = h[ver]; ~i; 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] == INF) cout << "-1" << endl;
    else cout << dist[n] << endl;
}

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

int main()
{
    cin >> n >> m;
    memset(h, -1, sizeof h);

    while (m -- )
    {
        int a, b, c;
        cin >> a >> b >> c;
        add(a, b, c);
    }

    dijkstra();

    return 0;
}

Bellman Ford

  可以求解不超过k条边的最短路径，通过k次循环，每次备份dist数组，每次遍历所有的边，通过上次dist数组更新本次dist数组，可以求取负边权的情况。时间复杂度是O(km)，因为每次经过k次迭代，每次迭代m条边。

SPFA

原理

  SPFA算法是队列优化的Bellman Ford算法，由于Bellman Ford算法需要k次更新所有的边，但是其中某些边在没有最短路径涉及时不需要更新。SPFA算法通过维护队列，将每次被更新的点加入队列，每次只更新队列内部的点，这样就减少了很多不必要点的更新操作。队列里是所有被更新过的点，因此可以维护st数组，当某个点被多个点更新时，就不用重复进入队列作为一下步扩展更新了。时间复杂度是O(nm)，但是实际上会比这个复杂度快很多，接近于O(m)。有可能会被特殊的图卡时间复杂度，如果没有卡，算是最短路径里面最好用的算法了。

  SPFA算法优化的一个重要原理是当元素出队的时候，已经在之前的过程中被多次更新，因此每次出队的时候，都是用当前很小的值去更新邻接点。

  实现过程中，使用循环队列，因为一共需要更新多少次不一定，如果使用n * m的队列太大了。

模板

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

using namespace std;

const int N = 100010;
const int INF = 0x3f3f3f3f;

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

//这里spfa使用了循环队列
void spfa()
{
    int hh = 0, tt = 1;
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;
    q[0] = 1;
    st[1] = true;

    while (hh != tt)
    {
        int t = q[hh ++ ];
        if (hh == N) hh = 0;

        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[tt ++ ] = j;
                    st[j] = true;
                }
                if (tt == N) tt = 0;
            }
        }
    }

    if (dist[n] >= INF / 2) cout << "impossible" << endl;
    else cout << dist[n] << endl;
}

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

int main()
{
    cin >> n >> m;
    memset(h, -1, sizeof h);

    while (m -- )
    {
        int a, b, c;
        cin >> a >> b >> c;
        add(a, b, c);
    }

    spfa();

    return 0;
}

SPFA判断负环

原理

  SPFA算法当队列不空的时候就会不断的更新图中路径的最短值，每次更新相当于多走一条边，当有负环的时候，某些节点一定会被无限次更新到负无穷，因此用cnt数组来记录每一个点的被更新次数，当某个点更新次数大于n – 1时，说明存在一条路径当更新n – 1次之后，还可以更小，这样就是存在负环了。开始时一定要把所有点都加入到队列中，否则只更新某一个点，也许去其他点的路径可以不经过负环，也就不会无限更新，就找不到负环来判断。

  SPFA判断负环可以用栈代替队列。这样做的好处是可以快速的将当前元素不停更新，这样如果进入负环，无限次的更新很快即可以满足cnt[j] >= n的条件，从而判断到负环。当超时的时候，可以考虑进行这种优化。另外，也可以设置一个经验值，比如2 n或者3 n以上，当SPFA算法更新次数超过这个次数的时候，也认为有负环，是一个大概率对但是不一定全对的优化。

模板

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

using namespace std;

const int N = 2010, M = 10010;

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

bool spfa()
{
    memset(dist, 0x3f, sizeof dist);

    queue<int> q;
    for (int i = 1; i <= n; i ++ )
        q.push(i);

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

        for (int i = h[t]; i != -1; i = ne[i])
        {
            int j = e[i];
            if (dist[t] + w[i] < dist[j])
            {
                dist[j] = dist[t] + w[i];
                cnt[j] = cnt[t] + 1 ;//表示当前路径下的该点已经经过了t + 1条边
                //cnt[j] ++ ; 也可以这样写，代表有某点被更新多于n - 1次也是有负环存在，但是效率低
                if (cnt[j] >= n) return true;
                q.push(j);
            }
        }
    }

    return false;
}

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

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()) cout << "Yes" << endl;
    else puts("No");

    return 0;
}

例题

AW.852 spfa判断负环（简单）