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;
}