最短路问题

2022-06-23 | 学习笔记 | 阅读 | 938 字 | 3 分钟

SPFA

时间复杂度

伪代码

Queue q
q.add(s) // s的距离初始为0, 其他顶点的距离初始为Infinity

while(!q.isEmpty())
    v = q.remove()
    for (w : v.adjs)  // w是v的邻接顶点
        if(dv + d(v, w) < dw)
            dw = dv + d(v, w)
            if(!q.contains(w)) //检查w是否在当前队列中，不在则入队
                q.add(w)

时间复杂度分析

SPFA算法过程中，顶点一层一层地入队出队，一张图最多有层(以为第层)，所以按层计，顶点最多入队次。第层顶点个数为，其余每层顶点数不会超过（第行所保证）。这里重点解释一下，一个顶点可能会通过不同的路径重复属于某一层，例如 $，$ ，没有第行检查的话，可以在第层顶点里出现两次。但有了第行，使得一个顶点只能在一层顶点里出现一次，否则算法复杂度将超过，后面还会讨论这种情况。当第一层有个，其余所有层都有个顶点时达到复杂度上限。

除第层外每一层顶点入队引起次松弛尝试，除第一层外的其他层的总时间复杂度为。因为第一层(顶点)引起的松弛尝试不会超过，所以总的时间复杂度为。

Acwing 1129.热浪

德克萨斯纯朴的民众们这个夏天正在遭受巨大的热浪！！！

他们的德克萨斯长角牛吃起来不错，可是它们并不是很擅长生产富含奶油的乳制品。

农夫 John 此时身先士卒地承担起向德克萨斯运送大量的营养冰凉的牛奶的重任，以减轻德克萨斯人忍受酷暑的痛苦。

John 已经研究过可以把牛奶从威斯康星运送到德克萨斯州的路线。

这些路线包括起始点和终点一共有个城镇，为了方便标号为到。

除了起点和终点外的每个城镇都由 双向道路 连向至少两个其它的城镇。

每条道路有一个通过费用（包括油费，过路费等等）。

给定一个地图，包含条直接连接个城镇的道路。

每条道路由道路的起点，终点和花费组成。

求从起始的城镇到终点的城镇最小的总费用。

输入格式

第一行: 个由空格隔开的整数: ;

第到第行: 第行描述第条道路，包含个由空格隔开的整数: 。

输出格式

一个单独的整数表示从到的最小总费用。

数据保证至少存在一条道路。

数据范围

,
,
,

输入样例：

输出样例：

思路:

可以看出是单源最短路问题, 选择 SPFA 或朴素dijkstra 或堆优化dijkstra

代码:

SPFA, 循环队列实现

...
const int N = 2510, M = 6200 *2 + 10;
int n,m,S,T;
int h[N], e[M], w[M] ,ne[M], idx;
int dist[N], q[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 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;
                    if(tt==n) tt = 0;
                    st[j] = true;
                }
            }
        }
    }
}
int main(){
    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;
    return 0;
}