Bellman-Ford求最短路和负环

时间复杂度：O(nm)O(nm)

【模板/笔记】Johnson算法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
bool Bellman_Ford()
{
    memset(dist, 0x3f, sizeof dist);
    for (int k = 1; k < n; k ++)
        for (int ver = 1; ver <= n; ver ++)
            for (int i = h[ver]; ~i; i = ne[i])
            {
                int to = e[i];
                if (dist[to] > dist[ver] + w[i])
                    dist[to] = dist[ver] + w[i];
            }


    for (int ver = 1; ver <= n; ver ++)
        for (int i = h[ver]; ~i; i = ne[i])
        {
            int to = e[i];
            if (dist[to] > dist[ver] + w[i])
                return true;
        }
    return false;
}

SPFA求最短路

时间复杂度：O(N×M)O(N \times M)（正常情况下效率接近线性，最坏情况下时间复杂度与 Bellman_Ford 相同）​

vector 存图

1
2
3
4
5
6
7
struct Edge
{
    int u, w;
};
vector<Edge> g[N];
int dist[N], n, m;
bitset<N> vis;
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
int spfa()
{
    queue<int> q;
    memset(dist, 0x3f3f3f, sizeof dist);
    dist[1] = 0, vis[1] = true;
    q.push(1);
    while (!q.empty())
    {
        int x = q.front(); q.pop();
        vis[x] = false;
        for (auto y : g[x])
        {
            int v = y.u, w = y.w;
            if (dist[v] > dist[x] + w)
            {
                dist[v] = dist[x] + w;
                if (!vis[v])
                {
                    q.push(v); vis[v] = true;
                }
            }
        }
    }
    if (dist[n] == INF) return -114514;
    else return dist[n];
}

链式前向星

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
bool SPFA(int st)
{
    memset(dist, 0x3f, sizeof dist), dist[st] = 0;
    que[++ tt] = st, vis[st] = true;

    while (hh <= tt)
    {
        int ver = que[hh ++];
        vis[ver] = false;

        for (int i = h[ver]; ~i; i = ne[i])
        {
            int to = e[i];
            if (dist[to] > dist[ver] + w[i])
            {
                dist[to] = dist[ver] + w[i];
                if (++ cnt[to] >= n) return true;
                if (!vis[to]) que[++ tt] = to;
            }
        }
    }
    return false;
}