2025年带负权边的单源最短路径算法

科技前沿 • 2025-02-17 18:12 • 阅读 41

大家好，我是讯享网，很高兴认识大家。

Bellman-Ford算法

算法步骤

扫描所有的边，若dist[y]>dist[x]+z，则用dist[x]+z更新dist[y]。
重复上述操作，知道没有更新操作发生

伪代码为： for k 次: for 所有边： dist[j]=min(dist[j],dist[i]+w);

讯享网

讯享网const int N=510,M=1e5+10,INF=0x3f3f3f3f; int n,m,k; int dist[N],last[N]; struct Edge{ 
    int a,b,w; }edges[M]; void bellmen_ford(){ 
    memset(dist,0x3f,sizeof dist); dist[1]=0; for(int i=0;i<k;i++){ 
    memcpy(last,dist,sizeof dist); // 注意这里需要复制一份dist，否则会串流 for(int j=1;j<=m;j++){ 
    Edge t=edges[j]; dist[t.b]=min(dist[t.b],last[t.a]+t.w); } } }

算法评价

算法的时间复杂度为O(mn)，一般用于稠密图。这个算法用的不多，一般用于求起点经过k条边到其他点的最短距离。

SPFA算法（稀疏图）

算法步骤

建立一个队列，将起点1加入队列
取出队友元素，扫描他的所有出边(x,y,w)，若dist[y]>dist[x]+w，则用dist[y]+w来更新dist[y]（松弛）,若y不在队列中，则y入队
重复上述操作，直到队列为空

伪代码为： queue.push(1); while(queue.size()) t=queue.top() queue.pop() 遍历与t相连的所有边(a,b,w) if(dist[b]>dist[t]+w) dist[b]>dist[t]+w 这里需要存储一个判断i是否在队列中的bool数组st[i]

C++代码如下

讯享网

讯享网const int N=1e5+10,INF=0x3f3f3f3f; int h[N],e[N],ne[N],w[N],idx; int dist[N]; int n,m; bool st[N]; // 这里的st[i]与之前算法不一样，用来表示i这里点是否在队列里面，因为这个算法中的顶点式可以重复进入队列的。 queue<int>q; 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[1]=0; 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]){ 
    int j=e[i]; if(dist[j]>dist[t]+w[i]){ 
    dist[j]=dist[t]+w[i]; if(!st[j]){ 
    st[j]=true; q.push(j); } } } } }

算法评价

算法的时间复杂度为O(km)，k是一个较小的数，但在有些特殊的图上，有可能会退化为O(mn)级别。

2025年带负权边的单源最短路径算法

Bellman-Ford算法

算法步骤

算法评价

SPFA算法（稀疏图）

算法步骤

算法评价

相关推荐