【算法杂谈】各种最短路算法模板

【先来一发SPFA】

int spfa_dfs(int u)
{
    vis[u]=1;
    for(int k=f[u]; k!=0; k=e[k].next)
    {
        int v=e[k].v,w=e[k].w;
        if( d[u]+w < d[v] )
        {
            d[v]=d[u]+w;
            if(!vis[v])
            {
                if(spfa_dfs(v))
                    return 1;
            }
            else
                return 1;
        }
    }
    vis[u]=0;
    return 0;
}

【再来一个Floyd】

for(int k=1;k<=n;k++)
 {
        for(int i=1;i<=n;i++)
        {    for(int j=1;j<=n;j++)
             {   
                mat[i][j]=min(mat[i][j],mat[i][k]+mat[k][j]);
             }
        }
 }