文章目录

邻接表存储 - 无权图的单源最短路算法（C++描述）

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define js ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
vector<int> g[100];
queue<int> qu;
int dist[100];
int path[100];
int main(){
    int n;
    cin>>n;
    memset(path,-1,sizeof(path));
    while(n--){
        int u,v;
        cin>>u>>v;
        g[u].push_back(v);
    }
    int m;
    bfs(m);
}
void bfs(int start){
    qu.push(start);
    while(!qu.empty()){
        int now=qu.front();
        qu.pop();
        for(auto nxt:g[now]){
            if(dist[nxt]==-1){
                dist[nxt]=dist[now]+1;
                path[nxt]=now;
                qu.push(nxt);
            }
        }
    }
}

Dijkstra算法：单源最短路（未使用堆优化）

#include<bits/stdc++.h>
using namespace std;
#define js ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
typedef long long ll;
struct Edge{
    int z,val,nexty;
}edge[200005];
int head[20000];
int cnt=0;
//链式前向星存边
void add(int a,int b,int c){
    cnt++;
    edge[cnt].z=b;
    edge[cnt].val=c;
    edge[cnt].nexty=head[a];
    head[a]=cnt;
}
int main(){
    bool vis[20000]={0};
    ll dis[20000];
    int n,m,s;
    int a,b,c;
    cin>>n>>m>>s;
    for(int i=1;i<=n;i++){
        dis[i]=0x7fffffff;
    }
    for(int i=0;i<m;i++){
        cin>>a>>b>>c;
        add(a,b,c);
    }
    int now=s;
    dis[s]=0;//起点
    ll minn=0x7fffffff;
    while(!vis[now]){
        vis[now]=1;
        for(int i=head[now];i;i=edge[i].nexty){
            if(!vis[edge[i].z]&&dis[edge[i].z]>dis[now]+edge[i].val){
                dis[edge[i].z]=dis[now]+edge[i].val;
            }
        }
        minn=0x7fffffff;
        for(int i=1;i<=n;i++){
            if(!vis[i]&&minn>dis[i]){
                minn=dis[i];
                now=i;
            }
        }
    }
    for(int i=1;i<=n;i++) cout<<dis[i]<<" ";
}

Dijkstra算法：单源最短路（使用堆优化）

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
struct Edge{
    int z,val,nexty;
}edge[1000000];
int head[200000];
ll dis[200000];
bool vis[200000]={0};
int cnt=0;
//链式前向星存边
inline void add(int a,int b,int c){
    cnt++;
    edge[cnt].z=b;
    edge[cnt].val=c;
    edge[cnt].nexty=head[a];
    head[a]=cnt;
}
struct node{
    int dis;
    int pos;
    bool operator<(const node &x)const{
        return x.dis<dis;
    }
};
priority_queue<node> q;
int main(){
    int n,m,s;
    int a,b,c;
    scanf("%d%d%d",&n,&m,&s);
    for(int i=1;i<=n;i++){
        dis[i]=0x7fffffff;
    }
    for(int i=0;i<m;i++){
        scanf("%d%d%d",&a,&b,&c);
        add(a,b,c);
    }
    dis[s]=0;//起点
    q.push((node){0,s});
    while(!q.empty()){
        node tmp=q.top();
        q.pop();
        int x=tmp.pos,d=tmp.dis;
        if(vis[x]) continue;
        vis[x]=1;
        for(int i=head[x];i;i=edge[i].nexty){
            int y=edge[i].z;
            if(dis[y]>dis[x]+edge[i].val){
                dis[y]=dis[x]+edge[i].val;
                if(!vis[y]){
                    q.push((node){dis[y],y});
                }
            }
        }
    }
    for(int i=1;i<=n;i++) printf("%d ",dis[i]);
}

Floyd算法：多源最短路

#include<bits/stdc++.h>
#include<algorithm>
#define int long long
using namespace std;
int dis[105][105];
typedef long long ll;
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
	int n,m,k;
	cin>>n>>m>>k;
	//先初始化dis数组为无穷大 
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			dis[i][j]=0x7fffffff;
		}
	}
	//读入图，更新距离 
	for(int i=0;i<m;i++){
		int a,b,c;
		cin>>a>>b>>c;
		dis[a][b]=min(dis[a][b],c);//对付重边 
	}
	//三重循环更新最小距离 
	for(int k=1;k<=n;k++){
		for(int i=1;i<=n;i++){
			if(i==k||dis[i][k]==0x7fffffff) continue;
			for(int j=1;j<=n;j++){
				if(dis[i][k]+dis[k][j]<dis[i][j]){
					dis[i][j]=dis[i][k]+dis[k][j];
				}
			}
		}
	}
	while(k--){
		int a,b;
		cin>>a>>b;
		if(dis[a][b]==0||dis[a][b]==0x7fffffff){
			cout<<"Nothing to say!"<<endl;
		}else{
			cout<<dis[a][b]<<endl;
		}
	}
	return 0;
}

SPFA算法：可以求负权图

用dis数组记录源点到有向图上任意一点距离，其中源点到自身距离为0，到其他点距离为INF。将源点入队，并重复以下步骤：

  • 队首x出队
  • 遍历所有以队首为起点的有向边(x,i)，若dis[x]+w(x,i)<dis[i]，则更新dis[i]
  • 如果点i不在队列中，则i入队
  • 若队列为空，跳出循环；否则执行1 
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define js ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
typedef long long ll;
struct Edge{
    int to,val,nexty;
}edge[200005];
int head[100005],cnt;
void addedge(int u,int v,int val){
    cnt++;
    edge[cnt].to=v;
    edge[cnt].val=val;
    edge[cnt].nexty=head[u];
    head[u]=cnt;
}
int n,m,s;
int dis[100005],vis[100005];
const int inf=0x7fffffff;
void spfa();
signed main(){
    cin>>n>>m>>s;
    for(int i=1;i<=m;i++){
        int u,v,val;
        cin>>u>>v>>val;
        addedge(u,v,val);
    }
    spfa();
    for(int i=1;i<=n;i++){
        if(i==s) cout<<0<<" ";
        else cout<<dis[i]<<" ";
    }
    return 0;
}
void spfa(){
    queue<int> qu;
    for(int i=1;i<=n;i++){
        dis[i]=inf;
        vis[i]=0;
    }
    qu.push(s);dis[s]=0;vis[s]=1;
    //vis[i]表示i是否在队列中
    while(!qu.empty()){
        int u=qu.front();
        qu.pop();
        vis[u]=0;
        for(int i=head[u];i;i=edge[i].nexty){
            int v=edge[i].to;
            if(dis[v]>dis[u]+edge[i].val){
                dis[v]=dis[u]+edge[i].val;
                if(vis[v]==0){
                    vis[v]=1;
                    qu.push(v);
                }
            }
        }
    }
}