最短路各种算法总结

备注

对于所有的算法，大部分都是用邻接表存储，如果有特殊会指出，并且我们在分析时间复杂度的时候指定顶点个数为$N$，边的条数为$M$。

单链表的建图方式

带权边

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

不带权

void add(int a, int b){
    e[idx] = b, ne[idx] = h[a], h[a] = idx ++;
}
1
2
3

！！！一定要记得初始化邻接表头为$-1$

1.堆优化版$dijkstra$ 算法

注意

不能处理有负权边的最短路

时间复杂度

$O(N\ast \log M)$

模板

求$s$到$t$的最短路

int dijkstra(int s, int t){
    memset(dist, 127, sizeof (dist));
    memset(st, false, sizeof st);
    dist[s] = 0;
    priority_queue<PII, vector<PII>, greater<PII>>q;
    q.push({0, s});
    while(q.size()){
        auto it = q.top();
        q.pop();
        int ver = it.second;
        if(st[ver]) continue;
        st[ver] = true;
        for(int i = h[ver]; ~i; i = ne[i]){
            int j = e[i], k = w[i];
            if(dist[j] > dist[ver] + k){
                dist[j] = dist[ver] + k;
                q.push({dist[j], j});
            } 
        }
    }
    if(dist[t] > 1e9) return -1;//这里是大于一个边界数，根据题目而定
    return dist[t];
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

$2.Bellman$ _ $Ford$算法

注意

可以求带负权边最短路，而且可以求有边数限制的最短路， 也可以判断有无负环

时间复杂度

$O(N\ast M)$

模板

备注

存图方式：用结构体存边即可

struct edge{
    int a, b, c;
}e[M];//a -> b有一条边权为c的边
1
2
3

1.求$s$到$t$的最短路

如果返回结果为一个很大的数，就是不存在最短路，这个很大的数根据题意来

int Bellman_Ford(int s, int t){
    memset(dist, 127, sizeof dist);
    dist[s] = 0;
    for(int i = 1; i <= n - 1; i ++ ){
        for(int j = 1; j <= m; j ++ ){
            int a = e[j].a, b = e[j].b, c = e[j].c;
            dist[b] = min(dist[b], dist[a] + c);
        }
    }
    return dist[t];
}
1
2
3
4
5
6
7
8
9
10
11

2.求从$s$到$t$，限制经过$k$条边的最短路

如果返回结果为一个很大的数，就是不存在最短路，这个很大的数根据题意来

int Bellman_Ford(int s, int t, int k){
    memset(dist, 127, sizeof dist);
    dist[s] = 0;
    for(int i = 1; i <= k; i ++ ){
        memcpy(pre, dist, sizeof dist);
        for(int j = 1; j <= m; j ++ ){
            int a = e[j].a, b = e[j].b, c = e[j].c;
            dist[b] = min(dist[b], pre[a] + c);
        }
    }
    return dist[t];
}
1
2
3
4
5
6
7
8
9
10
11
12

3.$Spfa$算法

注意

可以求带负权边最短路，而且可以判断有无负环

时间复杂度

$O(N\ast M)$

模板

1.求$s$到$t$的最短路

int spfa(int s, int t){
    queue<int>q;
    q.push(s);
    st[s] = 1;
    memset(dist, 127, sizeof dist);
    dist[s] = 0;
    while(q.size()){
        int ver = q.front();q.pop();st[ver] = 0;
        for(int i = h[ver]; ~i; i = ne[i]){
            int j = e[i], k = w[i];
            if(dist[j] > dist[ver] + k){
                dist[j] = dist[ver] + k;
                if(!st[j]){
                    q.push(j);
                    st[j] = 1;
                }
            }
        }
    }
    return dist[t];
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

2.判断有无负环

bool spfa(){
    memset(dist, 127, sizeof dist);
    dist[1] = 0;
    queue<int>q;
    for(int i = 1; i <= n; i ++ ) q.push(i), st[i] = 1;
    while(q.size()){
        int ver = q.front();
        q.pop();st[ver] = 0;
        for(int i = h[ver]; ~i; i = ne[i]){
            int j = e[i], k = w[i];
            if(dist[j] > dist[ver] + k){
                cnt[j] = cnt[ver] + 1;
                if(cnt[j] >= n) return true;
                dist[j] = dist[ver] + k;
                if(!st[j]){
                    q.push(j);
                    st[j] = 1;
                }
            }
        }
    }
    return false;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

$4.Floyd$算法

备注

这是求多源最短路的算法，我们用邻接矩阵存图。

时间复杂度

$O(N\ast N\ast N)$

模板

1.初始化邻接矩阵

    for(int i = 1; i <= n; i ++ )
    {
        for(int j = 1; j <= n; j ++ )
        {
            if(i == j) d[i][j] = 0;
            else d[i][j] = INF;
        }
    }
1
2
3
4
5
6
7
8

2.求多源最短路

void Flyod()
{
    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]);
            }
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13

5.双端$BFS$算法

备注

解决边权为$1$或者$0$的最短路问题

时间复杂度

$O(N)$

模板

int bfs(int s, int t){
    memset(dist, 127, sizeof dist);
    memset(st, 0, sizeof st);
    deque<int>q;
    dist[s] = 0;
    q.push_back(s);
    while(q.size()){
        int ver = q.front();
        q.pop_front();
        if(st[ver]) continue;
        st[ver] = true;
        for(int i = h[ver]; ~i; i = ne[i]){
            int j = e[i], d = w[i];
            if(dist[j] > dist[ver] + d){
                dist[j] = dist[ver] + d;
                if(d == 1) q.push_back(j);
                else q.push_front(j);
            }
        }
    }
    return dist[t];//如果是2139062143就是不存在最短路
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22