SPFA

#include<bits/stdc++.h>
using namespace std;
struct Edge
{
	int to,next,dis;
};//存边的数组 
Edge a[100010];
int pre[100010];
int cnt;//a数组的下标 
int d[100010];//存储每个点到顶点的最短路 
void add(int u,int v,int val)
{
	cnt++;
	a[cnt].to=v;
	a[cnt].dis=val;
	a[cnt].next=pre[u];
	pre[u]=cnt;
}
queue<int> q;//队列：存储经过的点
bool f[20010];//**标记哪些点在队列里
void spfa()
{

	memset(d,0x3f3f3f3f,sizeof(d));
	d[1]=0;
	q.push(1);
	f[1]=true ;
	while(!q.empty())
	{
		int u=q.front();
		for(int i=pre[u];i;i=a[i].next)
		{
			int v=a[i].to;
			if(d[u]+a[i].dis<d[v])
			{
				d[v] = d[u] +a[i].dis;
				if(!f[v]){
					q.push(v);
					f[v]=true;
				} 
			}
		} 
		q.pop();
		f[u] = false;
	} 
		
} 

Dijkstra

#include<bits/stdc++.h>
using namespace std;
const int INF = 0x3f3f3f3f;
const int MAXN = 60;
struct Edge
{
	int to,next,dis;
}edge[10000];
struct Node
{
	int dis,id;
	bool operator < (const Node &x) const
	{
		return x.dis<dis;
	}
};
int dis[MAXN];//源点到各个点的最短路长度
bool vis[MAXN];
int n,m,s,head[60],cnt;

void add_edge(int u,int v,int w)
{
	edge[++cnt].to=v;
	edge[cnt].dis=w;
	edge[cnt].next=head[u];
	head[u]=cnt;
}
void dijkstra()
{
	memset(dis,0x3f,sizeof(dis));
	priority_queue <Node> q;
	Node tmp;
	tmp.id=1;
	tmp.dis=0;
	q.push(tmp);
	dis[1]=0;
	while(!q.empty())
	{
		tmp=q.top();
		q.pop();
		if(vis[tmp.id])
			continue;
		vis[tmp.id]=1;
		for(int i=head[tmp.id];i;i=edge[i].next)
			if(dis[edge[i].to]>dis[tmp.id]+edge[i].dis)
			{
				dis[edge[i].to]=dis[tmp.id]+edge[i].dis;
				if(!vis[edge[i].to])
					q.push((Node){dis[edge[i].to],edge[i].to});
			}
	}
}

Floyd

#include<bits/stdc++.h>
using namespace std;
const int N=110,INF=0x3f3f3f3f;
int d[N][N];
int n,m;
int main() {
	cin>>n>>m;
	memset(d,0x3f,sizeof(d));
	for(int i=1; i<=n; i++)
		d[i][i]=0;
	int u,v,l;
	for(int i=1; i<=m; i++) {
		cin>>u>>v>>l;
		d[u][v]=l;
	}
	for(int k=1; k<=n; k++) {
		for(int i=1; i<=n; i++) {
			for(int j=1; j<=n; j++) {
				if(d[i][k]!=INF&&d[k][j]!=INF) {
					d[i][j] =min(d[i][j],d[i][k]+d[k][j]);
				}
			}
		}
	}
	for(int i=1; i<=n; i++) {
		for(int j=1; j<=n; j++) {
			cout<<d[i][j]<<" ";//有向图
		}
			cout<<endl;
	}
	return 0;
}