当前位置：首页 > article >正文

搜索与图论复习2最短路

article 2025/2/3 23:54:15

单源最短路---所有边权是正数(Dijkstra算法O(n^2)--稠密图(邻接矩阵)和堆优化的Dijkstra算法O(mlogn)--稀疏图(邻接表)) 或存在负边权(Bellman-ford贝尔曼福特算法O(nm)和SPFA一般O(m) 最坏O(nm) )

多源最短路---Floyd算法O(n^3)

一、迪杰斯特拉算法(Dijkstra)：1dist[1]=0,dist[v]=正无穷。2for(v的0~n)，s是当前已经确定最短路径的点，t是不在s中的距离最近的点，t放进s中，用t更新其他点的距离（dist[x]>dist[t]+w）更新。通过邻接矩阵存图。

#include<iostream>
#include<cstring> 
using namespace std;
const int N=510;
int n,m;
int g[N][N];
int dist[N];
bool st[N];//确定最短路 
int dijkstra(){
	memset(dist,0x3f,sizeof(dist));
	dist[1]=0;//起点 
	for(int i=0;i<n;i++){
		int t=-1;
		for(int j=1;j<=n;j++){
			if(!st[j]&&(t==-1||dist[t]>dist[j]))t=j;//找到dist最小的点 
		}
		if(t==n)break;//优化 
		st[t]=true;
		for(int j=1;j<=n;j++){
			dist[j]=min(dist[j],dist[t]+g[t][j]);
		}
	}
	if(dist[n]==0x3f3f3f3f)return -1;
	else return dist[n];
}
int main(){
	cin>>n>>m;
	memset(g,0x3f,sizeof(g));
	while(m--){
		int a,b,c;
		cin>>a>>b>>c;
		g[a][b]=min(g[a][b],c);
	}
	int t=dijkstra();
	cout<<t<<endl;
	
	return 0;
}

二、堆优化的迪杰斯特拉算法：优化在n个数中找距离最近的点O(n^2)用堆优化

#include<iostream>
#include<cstring> 
#include<queue> 
using namespace std;
typedef pair<int,int>PII;
const int N=150010;
int n,m;
int h[N],e[N],ne[N],idx,w[N];//权重 
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 dijkstra(){
	memset(dist,0x3f,sizeof(dist));
	dist[1]=0;//起点 
	priority_queue<PII,vector<PII>,greater<PII>>heap;
	heap.push({0,1});//从1点开始,0为距离 
	while(heap.size()){
		auto t=heap.top();
		heap.pop();
		int ver=t.second,distance=t.first;
		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({dist[j],j}); 
			}
		}
	}
	if(dist[n]==0x3f3f3f3f)return -1;
	else 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=dijkstra();
	cout<<t<<endl;
	
	return 0;
}

三、Bellman-Ford算法for循环n次，(备份)for所有边a,b,w表示所有a到b的边权值为w，(松弛)，处理有福权边，能判断是否有负环(但是一般用SPFA做)

- 第 k 次松弛：找到经过最多 k 条边的最短路径。
通过多次松弛，算法可以逐步覆盖从起点到所有节点的所有可能路径

#include<iostream>
#include<cstring>
using namespace std;
const int N=510,M=10010;
int n,m,k;
int dist[N],backup[N];
struct Edge{
    int a,b,w;
}edges[M];
int bellman_ford(){
    memset(dist,0x3f,sizeof(dist));
    dist[1]=0;
    for(int i=0;i<k;i++){
        memcpy(backup,dist,sizeof(dist));
        for(int j=0;j<m;j++){
            int a=edges[j].a,b=edges[j].b,w=edges[j].w;
            dist[b]=min(dist[b],backup[a]+w);
        }
    }
    if(dist[n]>0x3f3f3f3f/2)return -0x3f3f3f3f;
    else return dist[n];
}
int main(){
    cin>>n>>m>>k;
    for(int i=0;i<m;i++){
        int a,b,c;
        cin>>a>>b>>c;
        edges[i]={a,b,c};
    }
    int t=bellman_ford();
    if(t==-0x3f3f3f3f)cout<<"impossible"<<endl;
    else cout<<t<<endl;
    return 0;
}

四、SPFA算法：用队列，只要有变小就取出队头，更新t的所有出边，成功就加入队列（更新过谁就拿谁来操作）通过队列优化 Bellman-Ford 算法，只对距离发生变化的节点进行松弛操作。

#include<iostream>
#include<cstring>
#include<queue>
using namespace std;
int n,m;
const int N=100010;
int dist[N];
bool st[N];
int h[N],e[N],ne[N],idx,w[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]){
            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;
                }
            }
        }
    }
    if(dist[n]==0x3f3f3f3f)return -0x3f3f3f3f;
    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)cout<<"impossible"<<endl;
    else cout<<t<<endl;
    return 0;
}

补充负环判断：维护cnt[x]=cnt[t]+1，的数组，如果cnt[x]>=n存在负环。

#include<iostream>
#include<cstring>
#include<queue>
using namespace std;
const int N=2010,M=10010;
int h[N],e[M],ne[M],idx,w[M];
int dist[N],cnt[N];
bool st[N];
int n,m;
void add(int a,int b,int c){
    e[idx]=b,w[idx]=c,ne[idx]=h[a],h[a]=idx++;
}
int spfa(){
    queue<int>q;
    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(){
    cin.tie(0),cout.tie(0);
    ios::sync_with_stdio(false);
    cin>>n>>m;
    memset(h,-1,sizeof(h));
    while(m--){
        int a,b,c;
        cin>>a>>b>>c;
        add(a,b,c);
    }
    if(spfa())cout<<"Yes"<<endl;
    else cout<<"No"<<endl;
    return 0;
}

五、Floyd算法：基于动态规划三层for枚举d(i,j)=min(d(i,j)，d(i,k)+d(k,j))。

#include<iostream>
#include<cstring> 
using namespace std;
const int N=210,INF=1e9;
int n,m,Q;
int d[N][N];
void floyd(){
	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 main(){
	cin>>n>>m>>Q;
	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;
		}
	}
	while(m--){
		int a,b,w;
		cin>>a>>b>>w;
		d[a][b]=min(d[a][b],w);
	}
	floyd();
	while(Q--){
		int a,b;
		cin>>a>>b;
		if(d[a][b]>INF/2)cout<<"impossible"<<endl;
		else cout<<d[a][b]<<endl;
	}
	return 0;
}

查看全文

http://www.kler.cn/a/530377.html