最短路

声明： 个点， 条边 稠密图用邻接矩阵，稀疏图用邻接表

dijkstra算法

不适用于有负权边的情况，复杂度为 或

有朴素版本和堆(优先队列)优化版本

朴素版本

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
int dijkstra()
{
    memset(dist, 0x3f, sizeof(dist));
    dist[1] = 0;
    for(int i = 1; i < n; i ++ )  // 因为第一个点已经计算过了，所以循环n-1次即可
    {
        int t = -1;
        for(int j = 1; j <= n; j ++ )
            if(!st[j] && (t == -1 || dist[j] < dist[t]))
                    t = j;

        for(int j = 1; j <= n; j ++ )
            dist[j] = min(dist[j], dist[t] + g[t][j]); 
        st[t] = true;
    }
    if(dist[n] == 0x3f3f3f3f)  return -1;
    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
24
25
26
27
28
29
30
31
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));  //  初始化距离为正无穷
    priority_queue<PII, vector<PII>, greater<PII> > heap;  // 元素种类为PII的小根堆
    dist[1] = 0;
    heap.push(make_pair(0, 1));  //  由于小根堆中的pair会默认按第一个元素排序，所以这里将距离存到前面
    while(heap.size())
    {
        auto 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] )  //  注意i初始化ver的头指针h[ver]
        {
            int j = e[i];  // 取点
            if(distance + w[i] < dist[j]) 
            {
                dist[j] = distance + w[i];
             heap.push(make_pair(dist[j], j));
            }
        }
    }
    if(dist[n] == 0x3f3f3f3f)  return -1;
    else return dist[n];
}

vector存图

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
#include <bits/stdc++.h>
#define debug(x) cout << #x << " = " << x << endl
#define xx first
#define yy second
using namespace std;

typedef pair<int, int> PII;
typedef long long LL;

const int N = 1e6 + 5, mod = 1e9 + 7;
//const double esp = 1e-6;
int dist[N];
bool st[N];
int n, m;
int main()
{
    cin >> n >> m;
    vector<vector<PII>> g(n);
    for(int i = 1; i <= m; i ++)
    {
        int a, b, c;
        cin >> a >> b >> c;
        a --, b --;
        g[a].push_back({b, c});
    }
    auto dijkstra = [&]()
    {
        memset(dist, 0x3f, sizeof dist);
        memset(st, false, sizeof st);
        priority_queue<PII, vector<PII>, greater<PII> > q;
        dist[0] = 0;
        q.push({0, 0});
        while(q.size())
        {
            auto t = q.top();
            q.pop();
            if(st[t.yy]) continue;
            st[t.yy] = true; 
            for(auto [u, v] : g[t.yy])
            {
                if(dist[u] > t.xx + v)
                {
                    dist[u] = t.xx + v;
                    q.push({dist[u], u});
                }
            }
        }
    };
    dijkstra();
    if(dist[n - 1] == 0x3f3f3f3f) cout << "-1";
    else cout << dist[n - 1] << '\n';
    return 0;
}

邮递员送信

邮递员去送信然后要求送信后再返回（有向边）

解法：

反向建边+跑两次dijkstra 正着走过去的时候用一遍dijkstra。 返回时就建个返图跑一遍dijkstra。 反图可以把所有结点的编号+n建在原图的体系中。

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
#include <iostream>
#include <cstring>
#include <queue>

using namespace std;

typedef long long LL;
typedef pair<int, int> PII;
const int N = 2e5 + 5;  //  数组记得开够
int n, m;
int h[N], ne[N], w[N], e[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 ++ ;
}

void dijkstra(int fir)
{   
    memset(dist, 0x3f, sizeof(dist));
    priority_queue<PII, vector<PII>, greater<PII> >heap;
    dist[fir] = 0;
    heap.push(make_pair(0, fir));
    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] > distance + w[i])
            {
                dist[j] = distance + w[i];
                heap.push(make_pair(dist[j], j));
            }
        }
    }
}

int main()
{
    cin >> n >> m;
    memset(h, -1, sizeof(h));
    while(m -- )
    {
        int a, b, c;
        cin >> a >> b >> c;
        add(a, b, c);
        add(b + n, a + n, c);  //  建一个反图
    }
    dijkstra(1);
    LL res = 0;
    for(int i = 1; i <= n; i ++ )
    {
        res += dist[i];
    }
    dijkstra(1 + n);  //  反向跑一次dijkstra
    for(int i = 1 + n; i <= 2 * n; i ++ )
    {
        res += dist[i];
    }
    cout << res;
    return 0;
}

最短路计数

增加一个num数组进行计数

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
#include <iostream>
#include <cstring>
#include <queue>

using namespace std;

typedef long long LL;
typedef pair<int, int> PII;
const int N = 2e6 + 5, mod = 100003;
int n, m;
int h[N], ne[N], w[N], e[N], idx;
int dist[N], num[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 ++ ;
}

void dijkstra()
{
    memset(dist, 0x3f, sizeof(dist));
    dist[1] = 0;
    num[1] = 1;
    priority_queue<PII, vector<PII>, greater<PII> > heap;
    heap.push(make_pair(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] == distance + w[i])
            {
                num[j] = (num[j] + num[ver]) % mod;
            }
            if(dist[j] > distance + w[i])
            {
                dist[j] = distance + w[i];
                num[j] = num[ver];
                heap.push(make_pair(dist[j], j));
            }
        }
    }
}

int main()
{
    cin >> n >> m;
    memset(h, -1, sizeof(h));
    while(m -- )
    {
        int a, b;
        cin >> a >> b;
        if(a == b) continue;
        add(a, b, 1);
        add(b, a, 1);
    }
    dijkstra();
    for(int i = 1; i <= n; i ++ )
    {
        printf("%d\n", num[i]);
    }
    return 0;
}

Bellman-ford算法

适用于有负权边的情况

如果有负环，或限制最多走k次时可以用，大多数时候用SPFA完全替代

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
#include <iostream>
#include <cstring>

using namespace std;

const int N = 510, M = 10010;

int n, m, k;  //  n个点，m条边，走不超过k次

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

int dist[N], backup[N];

void Bellman_ford()
{
    memset(dist, 0x3f, sizeof(dist));
    dist[1] = 0;
    for(int i = 1; i <= k; i ++ )
    {
        memcpy(backup, dist, sizeof(dist));
        for(int j = 1; j <= m; j ++ )
        {
            Edge e = edge[j];
            dist[e.b] = min(dist[e.b], backup[e.a] + e.c);
        }
    }
}

int main()
{
    cin >> n >> m >> k;
    for(int i = 1; i <= m; i ++ )
    {
        int a, b, c;
        cin >> a >> b >> c;
        edge[i].a = a, edge[i].b = b, edge[i].c = c;
    }
    Bellman_ford();
    if(dist[n] > 0x3f3f3f3f / 2)  printf("impossible\n");
    else printf("%d\n", dist[n]);
    return 0;
}

SPFA算法

利用宽搜BFS进行优化

适用于有负权边的情况

如果存在负环则不能用

，最坏情况

朴素版本

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
#include <iostream>
#include <cstring>
#include <queue>

using namespace std;

const int N = 100010;

int n, m;
int e[N], w[N], ne[N], h[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())
    {
        int t = q.front();
        q.pop();
        st[t] = false;
        for(int i = h[t]; i != -1; i = ne[i])  // i = h[t]忘记写h了易错！！！
        {
            int j = e[i];
            if(dist[j] > dist[t] + w[i])
            {
                dist[j] = dist[t] + w[i];
                if(!st[j])
                {
                    q.push(j);  //  记得推进队列之中去
                    st[j] = true;
                }
            }
        }
    }
    return dist[n];
}

int main()
{
    cin >> n >> m;
    memset(h, -1, sizeof h);
    while(m -- )
    {
        int a, b, c;
        cin >> a >> b >> c;
        add(a, b, c);
    }
    int t = spfa();
    if(t == 0x3f3f3f3f)  printf("impossible\n");
    else printf("%d\n", t);
    return 0;
}

SPFA判断负环

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
#include <iostream>
#include <queue>
#include <iostream>
#include <cstring>

using namespace std;

const int N = 1e5 + 10;

int n, m;
int h[N], e[N], ne[N], w[N], idx;
int dist[N];
int 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()
{
    memset(dist, 0x3f, sizeof(dist));
    memset(cnt, 0, sizeof(cnt));
    queue <int> q;
    dist[1] = 0;
    //  如果题目说存在负环，那么需要循环一次将所有的点都加入队列之中
    //  如果是求是否存在从1开始的负环，那么只将1加入队列之中就可以了
    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;
}

int main()
{
    int t;
    cin >> t;
    while(t -- )
    {
        memset(h, -1, sizeof(h));
        memset(e, 0, sizeof(e));
        memset(ne, 0, sizeof(ne));
        memset(w, 0, sizeof(w));
        memset(st, 0, sizeof(st));
        idx = 0;
        cin >> n >> m;
        while(m -- )
        {
            int a, b, w;
            cin >> a >> b >> w;
            if(w >= 0)
            {
                add(a, b, w);
                add(b, a, w);
            }
            else  add(a, b, w); 
        }
        if(spfa())  printf("YES\n");
        else printf("NO\n");
    }
    return 0;
}

用 数组进行判断，如果 大于 说明存在负环使得求最短路时不断循环

时间复杂度 一般： 最坏：

多源汇最短路Floyd算法

时间复杂度 

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
#include <iostream>
#include <cstring>

using namespace std;

const int N = 300;
int n, m, k;
int dist[N][N];  //  注意只需要dist数组，无需g数组

void floyd()
{
    for(int k = 1; k <= n; k ++ )  // k写在最前面
        for(int i = 1; i <= n; i ++ )
            for(int j = 1; j <= n; j ++ )
                dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);  
    // 注意是dist[i][k]+dist[k][j]
}

int main()
{
    cin >> n >> m >> k;
    for(int i = 1; i <= n; i ++ )
    {
        for(int j = 1; j <= n; j ++ )
        {
            if(i == j)  dist[i][j] = 0;  //  不用memset进行初始化
            //  手动初始化使得dist[i][i] = 0
            else dist[i][j] = 0x3f3f3f3f;
        }
    }
    while(m -- )
    {
        int a, b, c;
        cin >> a >> b >> c;
        dist[a][b] = min(dist[a][b], c);  // 重边最小化操作
    }
    floyd(); 
    while(k -- )
    {
        int a, b;
        cin >> a >> b;
        if(dist[a][b] > 0x3f3f3f3f / 2)  printf("impossible\n");
        else printf("%d\n", dist[a][b]);
    }
    return 0;
}