2025-01-30单源最短路径建图方式

单源最短路径建图方式

1. 主要内容

1. SPFA算法模板

代码

#include<bits/stdc++.h>
using namespace std;

const int N = ..., M = ...; // 根据题目调整节点和边的数量
int h[N], e[M], w[M], ne[M], idx; // 链式前向星存储图
int dist[N], q[N]; // dist存储最短距离，q为循环队列
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 spfa(int start) { // SPFA算法
    memset(dist, 0x3f, sizeof dist); // 初始化距离为正无穷
    dist[start] = 0; // 起点距离为0
    int hh = 0, tt = 1;
    q[0] = start, st[start] = true; // 起点入队

    while (hh != tt) {
        int t = q[hh++];
        if (hh == N) hh = 0; // 队列循环操作
        st[t] = false; // 当前节点出队

        for (int i = h[t]; ~i; i = ne[i]) { // 遍历邻接表
            int j = e[i];
            if (dist[j] > dist[t] + w[i]) { // 更新距离
                dist[j] = dist[t] + w[i];
                if (!st[j]) { // 如果未入队，则入队
                    q[tt++] = j;
                    st[j] = true;
                    if (tt == N) tt = 0;
                }
            }
        }
    }
}

适用场景

无负权环的加权图：适用于边权可以为正或零的图，但不能有负权环。
稀疏图：当图的边数较少时（即边数 m 远小于 n2），SPFA 的效率较高。
需要频繁更新最短路径：例如在动态图中，边的权重可能会变化，SPFA 可以较快地重新计算最短路径。

时间复杂度

平均情况：O(m)，其中 m 是边的数量。
最坏情况：O(n⋅m)，其中 n 是节点数量。在某些特殊构造的图中（如所有节点都连成一条链），SPFA 的性能会退化到接近 O(n⋅m)。

数据规模

节点数 n：通常适用于 n≤10^5 的情况。
边数 m：通常适用于 m≤10^6 的情况。

优点

代码简单：实现起来相对容易，适合快速开发。
效率较高：在稀疏图中表现良好，尤其是在实际应用中，平均情况下效率较高。

缺点

容易被卡：在某些特殊构造的图中（如所有节点都连成一条链），SPFA 的性能会退化到接近 O(n⋅m)，可能会被卡成 O(n2) 的复杂度。

2. Dijkstra算法模板

代码

#include<bits/stdc++.h>
using namespace std;

const int N = ...; // 根据题目调整节点数量
int g[N][N]; // 邻接矩阵存储图
int dist[N]; // 存储最短距离
bool st[N]; // 标记数组

void dijkstra(int start) { // Dijkstra算法
    memset(dist, 0x3f, sizeof dist); // 初始化距离为正无穷
    dist[start] = 0; // 起点距离为0

    for (int i = 0; i < n; i++) { // 遍历所有节点
        int t = -1;
        for (int j = 0; j < n; j++) { // 找到未访问的最短距离节点
            if (!st[j] && (t == -1 || dist[j] < dist[t])) {
                t = j;
            }
        }
        st[t] = true; // 标记为已访问

        for (int j = 0; j < n; j++) { // 更新邻接节点的距离
            dist[j] = min(dist[j], dist[t] + g[t][j]);
        }
    }
}

适用场景

非负权图：适用于所有边权非负的图。
稠密图：当图的边数较多时（接近 n2），Dijkstra 算法表现良好。
需要精确计算最短路径：适用于对最短路径精度要求较高的场景。

时间复杂度

朴素版本：O(n2)，其中 n 是节点数量。
堆优化版本：O(mlogn)，其中 m 是边的数量。

数据规模

节点数 n：朴素版本适用于 n≤10^3，堆优化版本适用于 n≤10^5。
边数 m：堆优化版本适用于 m≤10^6。

优点

稳定：时间复杂度稳定，不会像 SPFA 那样容易被卡。
适用范围广：适用于所有非负权图。

缺点

代码复杂度：堆优化版本的代码相对复杂，需要使用优先队列。
效率在稀疏图中不如 SPFA：在稀疏图中，SPFA 的平均性能通常优于 Dijkstra。

3. Floyd算法模板

代码

#include<bits/stdc++.h>
using namespace std;

const int N = ...; // 根据题目调整节点数量
int d[N][N]; // 邻接矩阵存储图

void floyd() { // Floyd算法
    for (int k = 0; k < n; k++) { // 中间节点
        for (int i = 0; i < n; i++) { // 起点
            for (int j = 0; j < n; j++) { // 终点
                d[i][j] = min(d[i][j], d[i][k] + d[k][j]); // 更新最短距离
            }
        }
    }
}

适用场景

多源最短路径问题：适用于需要计算所有节点对之间的最短路径的情况。
小规模图：由于时间复杂度较高，适用于节点数量较小的图。

时间复杂度

固定复杂度：O(n3)，其中 n 是节点数量。

数据规模

节点数 n：通常适用于 n≤500 的情况。
边数 m：由于是多源最短路径问题，边数通常不是主要限制。

优点

代码简单：实现起来非常简单，适合快速开发。
功能强大：可以一次性计算所有节点对的最短路径。

缺点

时间复杂度高：不适用于大规模图。
空间复杂度高：需要 O(n2) 的空间来存储邻接矩阵。

4. BFS算法模板（适用于无权图）

代码

#include<bits/stdc++.h>
using namespace std;

const int N = ...; // 根据题目调整节点数量
bool g[N][N]; // 邻接矩阵存储图
int dist[N]; // 存储最短距离
int q[N]; // 循环队列

void bfs(int start) { // BFS算法
    memset(dist, 0x3f, sizeof dist); // 初始化距离为正无穷
    dist[start] = 0; // 起点距离为0
    int hh = 0, tt = 1;
    q[0] = start; // 起点入队

    while (hh != tt) {
        int t = q[hh++];
        if (hh == N) hh = 0; // 队列循环操作

        for (int i = 0; i < n; i++) { // 遍历所有节点
            if (g[t][i] && dist[i] > dist[t] + 1) { // 如果有边且距离更短
                dist[i] = dist[t] + 1; // 更新距离
                q[tt++] = i; // 入队
                if (tt == N) tt = 0;
            }
        }
    }
}

适用场景

无权图：适用于所有边权为 1 的无权图。
稀疏图：在稀疏图中表现良好，尤其是当图的边数较少时。

时间复杂度

固定复杂度：O(n+m)，其中 n 是节点数量，m 是边的数量。

数据规模

节点数 n：通常适用于 n≤10^5 的情况。
边数 m：通常适用于 m≤10^6 的情况。

优点

代码简单：实现起来非常简单。
效率高：在无权图中，时间复杂度为 O(n+m)，非常高效。

缺点

仅适用于无权图：不能处理有权图。

5. Dijkstra算法（堆优化版）模板

代码

#include<bits/stdc++.h>
using namespace std;

const int N = ..., M = ...; // 根据题目调整节点和边的数量
int h[N], e[M], w[M], ne[M], idx; // 链式前向星存储图
int dist[N]; // 存储最短距离
bool st[N]; // 标记数组
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> pq; // 小根堆

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

void dijkstra(int start) { // Dijkstra算法（堆优化版）
    memset(dist, 0x3f, sizeof dist); // 初始化距离为正无穷
    dist[start] = 0; // 起点距离为0
    pq.push({0, start}); // 起点入堆

    while (!pq.empty()) {
        auto [d, t] = pq.top();
        pq.pop();

        if (st[t]) continue; // 如果已经访问过，则跳过
        st[t] = true;

        for (int i = h[t]; ~i; i = ne[i]) { // 遍历邻接表
            int j = e[i];
            if (dist[j] > dist[t] + w[i]) { // 更新距离
                dist[j] = dist[t] + w[i];
                pq.push({dist[j], j}); // 入堆
            }
        }
    }
}

适用场景

非负权图：适用于所有边权非负的图。
大规模图：由于使用了优先队列优化，适用于大规模图。

时间复杂度

固定复杂度：O(mlogn)，其中 m 是边的数量，n 是节点数量。

数据规模

节点数 n：通常适用于 n≤10^5 的情况。
边数 m：通常适用于 m≤10^6 的情况。

优点

稳定：时间复杂度稳定，不会像 SPFA 那样容易被卡。
效率高：在大规模图中表现良好。

缺点

代码复杂度：需要使用优先队列，代码相对复杂。
空间复杂度：需要额外的空间来存储优先队列。

总结

SPFA：适合稀疏图和需要频繁更新的场景，但容易被卡。
Dijkstra（朴素）：适合小规模稠密图，代码简单但效率较低。
Dijkstra（堆优化）：适合大规模图，效率高但代码复杂。
Floyd：适合多源最短路径问题，适合小规模图。
BFS：适合无权图，效率高且代码简单。

在实际应用中，选择哪种算法需要根据具体问题的规模和特性来决定。

2. 例题

热浪

// https://blog.csdn.net/qq_30277239/article/details/106104598
#include<bits/stdc++.h>
using namespace std;

const int N=2510, M=6200*2+10;//
int h[N], // 结点对应链表表头
    e[M], // 链表结点值
    w[M], // 权重
    ne[M],// next指针
    idx;  // 下标
int n,m,S,T;
int dist[N], 
    q[N];     // 循环队列
bool st[N]; // 队列去重标记，true表示已经入队， false表示尚未入队

/*
spfa算法，时间复杂度比dijstra更低，但是容易被卡
*/
void spfa(){
    memset(dist, 0x3f, sizeof dist);//设为正无穷
    dist[S]=0;

    int hh=0, tt=1;
    q[0]=S, st[S]=true;

    while(hh!=tt){
        int t=q[hh++];
        if(hh==N) hh=0;
        st[t]=false;

        for(int i=h[t]; ~i; i=ne[i]){
            int j=e[i];
            if(dist[j]>dist[t]+w[i]){
                dist[j]=dist[t]+w[i];
                if(!st[j]){
                    q[tt++]=j;
                    st[j]=true;
                    if(tt==N) tt=0;
                }
            }
        }
    }

}

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

void work(){
    cin>>n>>m>>S>>T;

    memset(h, -1, sizeof h);
    for(int i=0;i<m;i++){
        int a,b,c;
        cin>>a>>b>>c;
        add(a,b,c), add(b,a,c);
    }

    spfa();

    cout<<dist[T]<<endl;
}

int main(){
    work();
    return 0;
}

香甜的黄油

// https://blog.csdn.net/2301_76180325/article/details/133858261
/*
 * 题目本身是一个多源最短路径问题，一般想到Floyd（n^3复杂度）， 但是观察问题规模n~800，所以要考虑优化
 * n次Dij：没区别，复杂度还是n^3
 * n次堆优化版Dij：复杂度是n*m*log(n)，可行
 * n次spfa：复杂度是n*m，可行，且代码相对简单，但是有概率会被卡
*/
#include<bits/stdc++.h>
using namespace std;

const int N=810, M=3000, INF=0x3f3f3f3f;

int n, p, m;
int h[N], e[M], w[M], ne[M], idx;
int id[N];
int dist[N], q[M];
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(int start){
    /*
     * 返回以start为起点到所有奶牛的单源最短路径之和
    */
    memset(dist,0x3f,sizeof dist);
    dist[start]=0;//起始结点初始化

    int hh=0,tt=1;
    q[0]=start,st[start]=true;//起始节点入队

    while(hh!=tt){
        int t=q[hh++];
        if(hh==N) hh=0;
        st[t]=false;//队头结点出队操作

        for(int i=h[t];~i;i=ne[i]){
            //遍历队头结点邻接表，更新距离
            int j=e[i];
            if(dist[j]>dist[t]+w[i]){
                dist[j]=dist[t]+w[i];
                if(!st[j]){
                    //修改最短路径但没入队的结点入队操作
                    q[tt++]=j;
                    if(tt==N) tt=0;
                    st[j]=true;
                }
            }
        }
    }

    int res=0;
    for(int i=0;i<n;i++){
        /*
         * 需要判断是否所有牛都可以到达这处牧场!!!!!!!!
        */
        int j=id[i];
        if(dist[j]==INF){
            res=INF;
            break;
        }
        else res+=dist[j];
    }

    return res;
}

void work(){
    cin>>n>>p>>m;

    for(int i=0;i<n;i++) cin>>id[i];

    memset(h,-1,sizeof h);
    for(int i=0;i<m;i++){
        int a,b,c;
        cin>>a>>b>>c;

        add(a,b,c),add(b,a,c);
    }

    int res=INF;
    for(int i=1;i<=p;i++) res=min(res, spfa(i));

    cout<<res<<endl;
}

int main(){
    work();
    return 0;
}

信使

// https://blog.csdn.net/xingchen_2008/article/details/129289330
// 这题属于单源最短路径，但数据较小，又因为弗洛伊德算法代码最简单，所以采用弗洛伊德
#include<bits/stdc++.h>
using namespace std;

const int N=110, INF=0x3f3f3f3f;
int d[N][N];
int n,m;

void work(){
    cin>>n>>m;

    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;

    for(int i=0;i<m;i++){
        int a,b,c;
        cin>>a>>b>>c;

        d[a][b]=d[b][a]=min(d[a][b],c);
    }

    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]);

    int res=0;
    for(int i=1;i<=n;i++)
        if(d[1][i]==INF){
            res=-1;
            break;
        }
        else{
            res=max(res,d[1][i]);
        }

    cout<<res<<endl;
}

int main(){
    work();
    return 0;
}

最小花费

// https://blog.csdn.net/Jacob0824/article/details/123061338
/*
 * p=100*w1*w2*w3*...*wn
 * 可以看成单源最长路径（实际上和最短路径类似，但是要注意一些初始化的细节），
 * 累乘加一个取对数的步骤，可以变成累加，辅助理解，实际操作可以直接求乘积最大值
 * 
 * 关于输入，一般规模超过十万（1e5）要采取scanf和printf
 * 需要适应一下
*/
#include<bits/stdc++.h>
using namespace std;

const int N=2010, M=1e5+10;
int n,m;
int S,T;
double g[N][N];
double dist[N];
bool st[N];

void dijkstra(){
    dist[S]=1;//乘法零元是1

    for(int i=1;i<=n;i++){
        //先找出目前没被遍历过的，值最大的结点
        int t=-1;   
        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]=max(dist[j], dist[t]*g[t][j]);
    }
}

void work(){
    scanf("%d%d", &n, &m);

    while(m--){
        int a,b,c;
        scanf("%d%d%d", &a, &b, &c);
        double d=(100.0-c)/100;//汇率
        //这里可以注意一下每条边的权重范围是0~1，不同范围适用的算法会不太一样
        g[a][b]=g[b][a]=max(d, g[a][b]);
    }

    scanf("%d%d", &S, &T);

    dijkstra();

    /*
     * "lf"表示double,
     * ".8"表示保留8位小数
    */
    printf("%.8lf\n", 100/dist[T]);
}

int main(){
    work();
    return 0;
}

最优乘车

// https://blog.csdn.net/qq_30277239/article/details/106148993
#include<bits/stdc++.h>
using namespace std;

const int M=110, N=510, INF=0x3f3f3f3f;
int m,n;
bool g[N][N];
int stop[N];
int dist[N];
int q[N];

void bfs(){
    memset(dist, 0x3f, sizeof dist);
    dist[1]=0;

    int hh=0, tt=1;
    q[0]=1;

    while(hh!=tt){
        int t=q[hh++];
        if(hh==N) hh=0;

        for(int i=1;i<=n;i++){
            if(g[t][i]&&dist[i]>dist[t]+1){
                dist[i]=dist[t]+1;
                q[tt++]=i;
                if(tt==N) tt=0;
            }
        }
    }
}

void work(){
    cin>>m>>n;

    string line;
    getline(cin, line);// 读取回车
    while(m--){
        getline(cin, line);

        stringstream ssin(line);
        int cnt=0,p;
        while(ssin>>p) stop[cnt++]=p;

        for(int i=0;i<cnt;i++)
            for(int j=i+1;j<cnt;j++)//注意，这里是单程巴士线路
                g[stop[i]][stop[j]]=true;
    }
     
    bfs();// 每条边的权重只能是0或者1，所以可以用bfs

    if(dist[n]==INF) puts("NO");
    else cout<<dist[n]-1<<endl;//换乘次数，等于坐的车辆数减1
}

int main(){
    work();
    return 0;
}

昂贵的聘礼

// https://blog.csdn.net/ju_ruo_ruo/article/details/125650770

#include<bits/stdc++.h>
using namespace std;

const int N=110, INF=0x3f3f3f3f;
int m,n;
int w[N][N], l[N];
int dist[N];
bool st[N];

int dijkstra(int down, int up){
    memset(dist, 0x3f, sizeof dist);
    memset(st, 0, sizeof st);

    dist[0]=0;//0作为起点，其实可以不考虑level，因为一定会遍历到，而且后续也不用修改dist

    for(int i=0;i<=n;i++){
        int t=-1;
        for(int j=0;j<=n;j++)
            if(!st[j]&&(t==-1||dist[j]<dist[t]))
                t=j;
        
        st[t]=true;//判重！！！！

        for(int j=0;j<=n;j++)
            if(l[j]>=down&&l[j]<=up)//判定是否在指定等级范围内
                dist[j]=min(dist[j], dist[t]+w[t][j]);
    }

    return dist[1];
}

void work(){
    cin>>m>>n;

    memset(w, 0x3f, sizeof w);
    for(int i=1;i<=n;i++){
        int p,cnt;
        cin>>p>>l[i]>>cnt;
        w[0][i]=min(w[0][i], p);//0号作为虚拟起点

        while(cnt--){
            int t,v;
            cin>>t>>v;
            w[t][i]=min(w[t][i], v);
        }
    }

    // 等级区间范围很小，所以我们可以遍历所有长度为2m，包含level[1]的小区间，求出最小值
    int res=INF;
    for(int i=l[1]-m;i<=l[1];i++) res=min(res, dijkstra(i,i+m));

    cout<<res<<endl;
}

int main(){
    work();
    return 0;
}

寒假练题计划 > 提高算法 > 图论 > 单源最短路径

#cpp #algorithm #ACwing #Dijsktra #SPFA #Floyd #BFS

2025-01-30单源最短路径建图方式

http://666xz666.github.io/2025/01/30/单源最短路径建图方式/

作者

666xz666

发布于

2025年1月30日

许可协议

2025-02-01单源最短路径的综合应用上一篇

2025-01-25区间合并下一篇