2.最短路问题

2.1单源最短路

2.1.1Dijkstra

2.1.1.1朴素版Dijkstra O($n^{2}$)

通常在==稠密图==之中使用

适用于求正权有向图中，源点到其余各个节点的最短路径。图中可以有环，但不能有负权边。

const int N = 510;

int n, m;
int g[N][N];
int dist[N];
bool st[N];//判断是否确定了最短路

int dijkstra()
{
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;

    for (int i = 0; i < n; i++)
    {
        int t = -1;//将t设置为-1 因为Dijkstra算法适用于不存在负权边的图

        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++)
            dist[j] = min(dist[j], dist[t] + g[t][j]);
    }

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

2.1.1.2堆优化版Dijkstra O(mlogn)

通常在==稀疏图==之中使用

适用于求正权有向图中，源点到其余各个节点的最短路径。

typedef pair<int, int> PII;

const int N = 1000010;

int n, m;
int h[N], e[N], w[N], ne[N], idx;
int dist[N];
bool 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(dist, 0x3f, sizeof dist);
    dist[1] = 0;
    priority_queue<PII, vector<PII>, greater<PII>> heap;
    heap.push({0, 1});

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

        int distance = t.first, ver = t.second;

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

        for(int i = h[ver]; i != -1; 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] == 0x3f3f3f3f) return -1;
    return dist[n];
}

2.1.2Bellman-ford O(nm)

可以计算==有边数限制==的最短路问题，模板为k条边

const int N = 510, M = 10010;

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

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

int bellman_ford()
{
    memset(dist, 0x3f, sizeof dist);

    dist[1] = 0;
    for(int i = 0; i < k; i ++) // 经过k条边的最短路
    {
        memcpy(backup, dist, sizeof dist);

        for(int j = 0; j < m; j ++)
        {
            Edge e = edges[j];
            int a = e.a, b = e.b, w = e.c;
            dist[b] = min(dist[b], backup[a] + w);
        }
    }

    // 应该放到主函数中判断，因为最短距离可能为负，不能用-1代表无解
    if(dist[n] > 0x3f3f3f3f / 2) return 0x3f3f3f3f;
    return dist[n];
}

2.1.3spfa 一般O(m), 最坏O(nm)

2.1.3.1spfa求最短路

const int N = 100010;

int n, m;
int h[N],w[N], e[N], ne[N],idx;
int dist[N];
bool st[N];//判断是否存在了队列中!!!

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

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

    queue<int> q;
    q.push(1);
    st[1] = true;//!!!

    while (q.size())
    {
        auto 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])     // 如果队列中已存在j，则不需要将j重复插入
                {
                    q.push(j);
                    st[j] = true;
                }
            }
        }
    }

    return dist[n];

}

2.1.3.2spfa判断负环

const int N = 2010, M = 10010;

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

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

bool 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])
                {
                    q.push(j);
                    st[j] = true;
                }
            }
        }
    }

    return false;
}

ps

（https://www.acwing.com/activity/content/code/content/48499/）

为什么dt数组不用初始化为0x3f3f3f3f，以及为什么初始化要把所有点入队？
答：dt数组的初始值是多少都不影响，因为dt数组在这里记录的不是最短路径。首先，我们理解初始化时为什么把所有点都加入队列中，在求1开始到n的最短路时，我们只把1入队了且让dt[1] = 0，目的是让1成为开始时唯一一个更新了dt数组的点，然后在根据已更新dt数组的这些点去更新他的出边（这就是spfa改良bellman的精髓）。但是负环可能不在点1的后继上（可以自行构造，把1放在拓扑图的中断位置，负环在点1的前面），所以要把所有点入队。所有看到这就懂了，dt数组的意义不是记录最短路径，而且来更新后继节点的，如果某个点的dt更新过了，那么就可以用这个点来更新他的后继节点（在求最短路问题里，一个点距离初始点的距离边短了，是不是尝试用这个点去更新他的后继节点，可能使得后继节点的最短距离也变小）。

2.2多源最短路 Floyd O($n^3$)

//初始化
d[i][j] = 0x3f3f3f3f (i != j)
        = 0          (i == j)

//循环
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]);

原理：动态规划

• 状态表示 d [k, i, j]
• 集合：所有从i出发，最终走到j，且中间只经过节点编号不超过k的所有路径
• 属性：路径长度的最小值
• 状态计算 d[k, i, j] = min(d[k - 1, i, j], d[k - 1, i, k] + d[k - 1, k, j])
• 所有不含节点k的路径 d[k - 1, i, j]
• 所有包含节点k的路径 d[k - 1, i, k] + d[k - 1, k, j]

d[k, i, j] = min(d[k - 1, i, j], d[k - 1, i, k] + d[k - 1, k, j])

最不济可以尝试滚动数组，但如果直接去掉最高维呢

d[i, j] = min(d[i, j], d[i, k] + d[k, j])

观察代码等价

这里等价不是很好想

a.多源汇最短路

b.传递闭包

概念

• 有向图
• 把所有能间接相连的点，直接相连

g[i, j]是无权图的表示形式，存在边为1，不存在为0

g[i, j] -> d[i, j]

步骤

• 初始化 d[i, j] = g[i, j]
• for(k) for(i) for(j)
• if(d[i, k] && d[k, j])
• d[i, j] = 1

c.找最小环

一般对于正权图而言

d.恰好经过k条边的最短路