图论-最短路

问题类型

有时我们需要在一张图上求一个点到另外一个点的最短距离，这时就要用到最短路算法了。

解决方案

假设我们已经有了一张n个点，m条边的图，我们要求s到t的最短路。
我们称s为源点，t为汇点，多源最短路即为有多个源点，单源最短路即为只有一个源点。

Floyd: 比较适用于多源最短路的情况。
我们用F[k][i][j]表示经过前k个点，从i到j的最短路。
所以F[k][i][j] = min(F[k - 1][i][j], F[k - 1][i][k] + F[k - 1][k][j])
然后我们发现第一维可以被滚动掉，但我们仍要先枚举k，在枚举i，j。
时间复杂度为O(n ^ 3)。

Dijkstra: 适用于单源最短路的问题。
如果我们有一条u -> v的长度为w的边，且Dis[u] + w < Dis[v]
那么我们从s -> u -> v的路径肯定比s -> v的路径优，所以我们更新Dis[v]的值。
我们把这个操作称为松弛操作。Dijkstra就是基于松弛操作的一个最短路算法。
我们对每个点都要松弛。我们每次找个Dis最小且未松弛过出边的点u，然后对它的出边进行松弛。
以上找点u的过程可以用堆来实现。时间复杂度为O(mlogm)。

SPFA: 适用于单源最短路的问题。
SPFA是Bellman-Ford的队列优化算法，也是基于松弛操作的。
我们每次对队列的队首元素u松弛它的出边(u,v)，如果被松弛了且v不在队列里，就把v加入队列。
时间复杂度为O(k*m)，k的最大值会被卡到n，但通常情况下平均值为2。
我们还可以对SPFA算法进行优化：SLF和LLL。
SLF: Small Label First，即我们在把v加入队列的时候，如果Dis[v] < Dis[队首]则加到队首，否则加到队尾。
LLL: Large Label Last，我们每次在取出队首元素的时候判断一下，如果Dis[队首] > 队列内Dis值的平均值，就把队首放入队尾，继续取出下一个队首。
SPFA还可以用来判负环，只要一个点进入队列>=n次，原图中就有负环。

最短路算法还可以用来解决差分约束系统的问题。
我们有n个变量，m个不等式，我们对于每个形如a - b ≥ c建一条b -> a的权值为c的边。
再新建一个超级源点，然后向每个点都连一条0的边。
然后我们对于这张有向图跑最长路，得到的Dis即为一组合法解。如果有正环则说明无解。

代码演示

Floyd

void Floyd()
{
    rep(i, 1, n) F[i][i] = 0;
    rep(k, 1, n)
        rep(i, 1, n)
            rep(j, 1, n)
                F[i][j] = min(F[i][j], F[i][k] + F[k][j]);
}

Dijkstra + Heap

priority_queue<pair<int, int>, vector<pair<int, int> >, greater<pair<int, int> > > Q;
void Dijkstra(int s)
{
    rep(i, 1, n) Dis[i] = INF, vis[i] = 0;
    Q.push(make_pair(0, s)); Dis[s] = 0;
    while (!Q.empty())
    {
        int u = Q.top().second; Q.pop();
        if (vis[u]) continue;
        vis[u] = 1;
        travel(i, u)
        {
            int v = edge[i].vet;
            if (!vis[v] && Dis[v] > Dis[u] + edge[i].val)
            {
                Dis[v] = Dis[u] + edge[i].val;
                Q.push(make_pair(Dis[v], v));
            }
        }
    }
}

SPFA

void SPFA(int s)
{
    int sum = 0, now = 1;
    rep(i, 1, n) vis[i] = 0, Dis[i] = INF;
    vis[s] = 1, Dis[s] = 0; Q.push_back(s);
    while (!Q.empty())
    {
        int u = Q.front(); Q.pop_front();
        if (Dis[u] * now > sum) //LLL
        {
            Q.push_back(u);
            continue;
        }
        sum -= Dis[u], now--;
        vis[u] = 0;
        travel(i, u)
        {
            int v = edge[i].vet;
            if (Dis[v] > Dis[u] + edge[i].val)
            {
                Dis[v] = Dis[u] + edge[i].val;
                if (vis[v]) continue;
                if (Q.empty() || Dis[v] > Dis[Q.front()]) Q.push_back(v); //SLF
                else Q.push_front(v);
                sum += Dis[v], now++; vis[v] = 1;
            }
        }
    }
}