【图论】最短路合集

更新于 分类于 ， 阅读次数： 本文字数： 7k 阅读时长 ≈ 6 分钟

图论中的最短路问题

前置知识：边(u,v)(u,v) 的松弛操作：dis(v)=min(dis(v),dis(u)+w)dis(v)=min(dis(v),dis(u)+w)

一般实际中写if((ll)d[v]>(ll)d[u]+w)，防止赋了0x7fffffff 的d 数组加法溢出；另一种方法是赋值0x3f3f3f3f

单源最短路径

即求解给定的单个出发点到图中其他点的最短路径

Bellman-Ford

可以负权，可以判断是否有负环，O(nm)O(nm) 。

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
27
//结构体+vector存边
bool bellmanford(int n, int s)
{
    d[s] = 0;
    bool flag;
    for (int i = 1; i <= n; i++)
    {
        flag = false;
        for (int u = 1; u <= n; u++) //对每条边试图进行松弛操作
        {
            for (auto it : G[u])
            {
                int v = it.to, w = it.val;
                if (d[v] > d[u] + w)
                {
                    d[v] = d[u] + w;
                    flag = true;
                }
            }
        }
        if (!flag)// 没有可以松弛的边时就停止算法
            break;
    }
    return flag; // 第 n 轮循环仍然可以松弛时说明 s 点可以抵达一个负环
    //注意，这里如果false说明s走不到负环，但是说不定有负环
    //如果仅仅是判负环，需要建一个到各个点距离为0的超级源点
}

SPFA

队列优化的Bellman-Ford，复杂度玄学

原理：松弛操作只可能在之前有过松弛操作的边端点产生

关于SPFA，它死了

出自某年NOI，因为造适当的数据可以将SPFA卡成最坏情况O(nm)O(nm)

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
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
queue<int> q;
bool vst[N];
int cnt[N];
bool spfa()
{
    d[s] = 0, vst[s] = true;
    q.push(s);
    while (!q.empty())
    {
        int u = q.front();
        q.pop();
        vst[u] = false;
        for (auto it : G[u])
        {
            int v = it.to, w = it.val;
            if (d[v] > d[u] + w)
            {
                d[v] = d[u] + w;
                
                /** 无重边的写法 **/
                cnt[v] = cnt[u] + 1; // 记录最短路经过的边数
                if (cnt[v] >= n) // 在不经过负环的情况下，最短路至多经过 n - 1 条边
                    return false; // 因此如果经过了多于 n 条边，一定说明经过了负环
                if (!vst[v]) //如果不在队列里就加入
                    q.push(v), vst[v] = true;
                
                /** 有重边的写法
                if (!vst[v])
                {
                    cnt[v]++; //有重边，记录入队次数
                    if (cnt[v] > n)
                        return false; // 有负环
                    q.push(v);
                    vst[v] = true;
                }
                **/
            }
        }
    }
    return true;
}

Dijkstra

没有负权边，时间复杂度O(mlog⁡m)O(m\log m)

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
27
28
typedef pair<int, int> P; //优先队列优化
int n, m, cnt, s; //s为源点
int d[N]; //记录最短路
bool vst[N];
void Dijkstra()
{
    priority_queue<P, vector<P>, greater<P>> dij; //声明优先队列
    dij.push(P(0, s)); //pair的first为当前最短距离，second为起点
    d[s] = 0; //其余置为INF
    while (!dij.empty()) 
    {
        int cur = dij.top().second; //取出目前距离最短的点
        dij.pop();
        if (vst[cur]) //vst的更新位置和入队是配套的，如果已经更新过这次的不会更优
            continue;
        vst[cur] = true;
        for (int i = head[cur]; ~i; i = edge[i].nxt) //从当前点遍历所有边
        {
            int v = edge[i].to, w = edge[i].val; //方便代码
            if (d[v] > d[cur] + w) 
            { 	//如果当前记录过的到to节点的距离比cur节点走这条路大
                d[v] = d[cur] + w; //更新
                dij.push(P(d[v], v)); //入队
                //pre[v] = cur; //如果需要记录最短路
            }
        }
    }
}

多源最短路径

Floyd

无负环图，多源最短路，时间复杂度O(n3)O(n^3)

1
2
3
4
5
6
7
8
9
//预处理将d[i][j]置为INF
for (int k = 1; k <= n; k++) //中转点k
    for (int i = 1; i <= n; i++) 
    {
        if (d[i][k] == INF || i == k)
            continue; //此中转点不通或是自环
        for (int j = 1; j <= n; j++) //如果有负权，需要判一下d[k][j]是否为INF
            d[i][j] = min((ll)d[i][j], (ll)d[i][k] + d[k][j]);
    }

  • 正权无向图求最小权值环：跑一遍找d[i][i]d[i][i] 最小的，O(n3)O(n^3) 。

  • 判断是否有负环：去掉i==ki==k ，跑完检查d[i][i]d[i] [i] 是否为负，若有为负的就有负环

  • 有向图判断任意两点是否连通：跑一遍，把minmin 改成或运算d[i][j]|=d[i][k]&d[k][j]，还可以用bitset 优化成O(n3w)O(\frac{n^3}{w}) ：

    1
    2
    3
    4
    for (int k = 1; k <= n; k++)
        for (int i = 1; i <= n; i++)
            if (d[i][k]) //如果i能通中转点k
                d[i] = d[i] | d[k]; //k能通的地方i都能通

  • 如果需要记录路径，记录的是pre[i][j]=kpre[i][j]=k 。

Johnson

  • 无负环图，复杂度O(nmlog⁡m)O(nm\log m) 。
  • 核心思想：修改路径权值使其能跑dijkstra
  • 步骤：
    • 新建0号节点，向每个点连一条长度为0的边
    • 跑一遍0号起点开始的Bellman-Ford，得到0号点到每个点的最短路dis[v]dis[v]
    • 将边(u,v)(u,v) 的边权修改为w+dis[u]−dis[v]w+dis[u]-dis[v]
    • 跑n轮dijkstra
  • 正确性：
    • 将修改后的边权，带入某条路径长的计算，结果为∑wi+dis[s]−dis[t]\sum w_i +dis[s]-dis[t]，ss 是起点，tt 是终点，因此最短路的性质没有改变。
    • BellmanFord对所有边进行了松弛操作dis[u]+w>=dis[v]dis[u]+w>=dis[v] ，保证修改后边权的非负性。
  • 注意：改spfa时判断轮数是n+1（添加了一个节点）
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
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
/* luoguP5905 */
struct Edge
{
    int to, val, nxt; //一般不用存边的起点
} edge[M];            //M看数据，未给就是N*N（N为节点数）
int head[N];          //初始化为-1
int tot;
void add_edge(int u, int v, int w) //添加一条u->v的权为w的边
{
    ++tot;
    edge[tot].to = v;
    edge[tot].val = w;
    edge[tot].nxt = head[u];
    head[u] = tot;
}
int dis[N];
int d[N][N];
int n, m;
bool vst[N];
int cnt[N];
bool spfa()
{
    queue<int> q;
    dis[0] = 0, vst[0] = true;
    q.push(0);
    while (!q.empty())
    {
        int u = q.front();
        q.pop(), vst[u] = false;
        for (int i = head[u]; ~i; i = edge[i].nxt)
        {
            int v = edge[i].to, w = edge[i].val;
            if (dis[v] > dis[u] + w)
            {
                dis[v] = dis[u] + w;
                if (!vst[v])
                {
                    cnt[v]++; //有重边，记录入队次数
                    if (cnt[v] > n)
                        return true;
                    q.push(v);
                    vst[v] = true;
                }
            }
        }
    }
    return false;
}
priority_queue<pii, vector<pii>, greater<pii>> q;
void dijkstra(int d[], int s)
{
    while (!q.empty())
        q.pop();
    for (int i = 1; i <= n; i++)
        vst[i] = false;
    d[s] = 0;
    q.push(make_pair(0, s));
    while (!q.empty())
    {
        int cur = q.top().second;
        q.pop();
        if (vst[cur])
            continue;
        vst[cur] = true;
        for (int i = head[cur]; ~i; i = edge[i].nxt)
        {
            int v = edge[i].to, w = edge[i].val;
            if (d[v] > (ll)d[cur] + w)
            {
                d[v] = d[cur] + w;
                q.push(make_pair(d[v], v));
            }
        }
    }
}
int main()
{
    read(n), read(m);
    for (int i = 0; i <= n; i++)
        head[i] = -1;
    int u, v, w;
    for (int i = 1; i <= m; i++)
    {
        read(u), read(v), read(w);
        add_edge(u, v, w);
    }
    for (int i = 1; i <= n; i++)
    {
        add_edge(0, i, 0); //注意，这里是有向边，如果用邻接矩阵，要把G[i][0]置为INF
        dis[i] = INF;
    }
    if (spfa()) //如果有负环
    {
        puts("-1");
        return 0;
    }
    for (int i = 1; i <= n; i++)
    {
        for (int j = head[i]; ~j; j = edge[j].nxt)
            edge[j].val += dis[i] - dis[edge[j].to];
        for (int j = 1; j <= n; j++)
            d[i][j] = INF;
    }
    for (int i = 1; i <= n; i++)
        dijkstra(d[i], i);
    for (int i = 1; i <= n; i++)
    {
        ll ans = 0;
        for (int j = 1; j <= n; j++)
            ans += (ll)j * (d[i][j] == INF ? INF : (d[i][j] - dis[i] + dis[j]));
       	// 这里的处理跟题目求解的东西有关，跟算法关系不大
        // 正常来说ij联通的话最短路就是d[i][j] - dis[i] + dis[j]
        printf("%lld\n", ans);
    }
    return 0;
}

分层图

图论题一般二维，ii 点到jj 点，有些题对这个过程有多种选择，引入第三维，将其“分层”，和dp中增加维数一个道理，在松弛操作中维护。

题目

P4568 JLOI2011 飞行路线 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

P1266 速度限制 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

k短路

建正反图，跑反图的最短路，再调整边取前k

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
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
bool vst[N];
double dis[N];
struct node
{
    int x;
    double v; //当前已走距离
    bool operator<(const node &rhs) const
    {
        return v + dis[x] > rhs.v + dis[rhs.x]; //A*的估价函数
    }
};
priority_queue<pii> Q; 
void dijkstra() //跑反图的最短路
{
    for (int i = 1; i <= n; i++)
        dis[i] = INF;
    dis[ed] = 0;
    Q.push(make_pair(0, ed));
    while (!Q.empty())
    {
        int cur = Q.top().second;
        Q.pop();
        if (vst[cur])
            continue;
        vst[cur] = true;
        for (int i = head[cur]; i; i = edge[i].nxt)
        {
            int v = edge[i].to;
            double w = edge[i].val;
            if (dis[v] > dis[cur] + w)
            {
                dis[v] = dis[cur] + w;
                Q.push(make_pair(dis[v], v));
            }
        }
    }
}

int cnt[N];
priority_queue<node> q;
//main函数里
dijkstra();
q.push({st, 0});
while (!q.empty())
{
    int cur=q.top().x, w=q.top().v;
    q.pop();
    cnt[cur]++;
    if (cur == ed && cnt[cur] == k)
    {
        printf("%.2lf\n", w);
        return 0;
    }
    if (cnt[cur] > k)
        continue;
    for (int i = head[cur]; i; i = edge[i].nxt)
        q.push({edge[i].to, edge[i].val + w});
}
printf("-1\n");

最短路计数

在Dijkstra中，做一点修改就行，很好懂直接看代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
...
int cnt[N];
void Dijkstra()
{
	...
    cnt[s] = 1;
    while (!dij.empty()) 
    {
        ...
        for (int i = head[cur]; ~i; i = edge[i].nxt) //从当前点遍历所有边
        {
            int v = edge[i].to, w = edge[i].val; //方便代码
            if (d[v] > d[cur] + w) 
            { 	//如果当前记录过的到to节点的距离比cur节点走这条路大
                d[v] = d[cur] + w; //更新
                dij.push(P(d[v], v)); //入队
                //pre[v] = cur; //如果需要记录最短路
                cnt[v] = cnt[cur];
            }
            else if (d[v] == d[cur] + w) // 很好理解，都是同样长度到达的
				cnt[v] += cnt[cur];
        }
    }
}

基于此可以延伸一些诸如次短路计数的鬼东西，可以把d 和cnt 都设置成二维，一个记最短路一个记次短路，分类讨论更新就行了。