1. 首页
2. 模板
3. 本页

最短路模板合集~（Dij+Floyd+Spfa）

自己整理的最短路模板，，对于最短路问题主要就是难在构图方面~~

//Dijstra   O(n^2)
//Dijkstra对于有负边权的最短路径不支持

void Dijstra()
{
    int i,j;
    for(i=0; i<n; ++i)
    {
        dis[i]=INF;
        vis[i]=0;
    }
    dis[1]=0;
    int v;
    for(i=1; i<=n; ++i)
    {
        min=INF;
        for(j=1; j<=n; ++j)
        {
            if(!vis[j]&&d[j]<min) //每次找点的过程，首先这个点没有被发现，然后找一个最小点
            {
                min=d[j];
                v=j;
            }
        }
        vis[v]=1;

        for(j=1; j<=n; ++j) //加进最小点后，再修改从源点没有被发现的点的最短路径
        {
            if(!vis[j]&&dis[v]+mp[v][j]<dis[j])
                dis[j]=dis[v]+mp[v][j];

        }

    }
    int ans=-1;
    for(i=1; i<=n; ++i)
        if(dis[i]>ans)
            ans=dis[i];

}

int main()
{


    for(int i=0; i<n; ++i) //初始化 类似prim
        for(int j=0; j<n; ++j)
        {
            if(i!=j)
                mp[i][j]=INF;
            else
                mp[i][j]=0;
        }


    while(m--)
    {
        mp[i][j]=mp[j][i]=~~;
    }



    Dijstra();


    return 0;

}


=============================================================


//Dijstra  优先队列+邻接表 

//优化后复杂度为O(mlogn)


    struct point
{
    int val,id;
    point(int id,int val):id(id),val(val) {}
    bool operator <(const point &x)const
    {
        return val>x.val;
    }
};
void dijkstra(int s)
{
    memset(vis,0,sizeof(vis));
    for(int i=0; i<n; i++)
        dis[i]=INF;

    priority_queue<point> q;
    q.push(point(s,0));
    vis[s]=true;
    dis[s]=0;
    while(!q.empty())
    {
        int cur=q.top().id;
        q.pop();
        vis[cur]=true;
        for(int i=head[cur]; i!=-1; i=e[i].next)
        {
            int id=e[i].to;
            if(!vis[id] && dis[cur]+e[i].val < dis[id])
            {
                dis[id]=dis[cur]+e[i].val;
                q.push(point(id,dis[id]));
            }
        }
    }
}




=============================================================

//Floyd    O(n^3)

    void Floyd()
{
    for(int i=0; i<n; ++i)
        for(int j=0; j<n; ++j)
            mp[i][j]=mp[j][i]=~~;


    for(int i=0; i<n; ++i)
        for(int j=0; j<n; ++j)
            for(int k=0; k<n; ++k)
                if(mp[j][k]>mp[j][i]+mp[i][k])
                    mp[j][k]=mp[j][i]+mp[i][k];


}


=============================================================


//Spfa 邻接矩阵   O(kE)E为边数，k一般为2或3
//可以计算带负环的回路


    void Spfa()
{
    int i,j;
    for(int i=0; i<n; ++i)
    {
        d[i]=INF;
        vis[i]=0;
    }

    queue<int>q;
    q.push(start);
    d[start]=0;
    vis[start]=1;
    while(!q.empty())
    {
        int v=q.front();
        q.pop();
        vis[v]=0;   // 这点别忘记

        for(i=0; i<n; ++i)
        {
            if(d[i]>d[v]+mp[v][i])
            {
                d[i]=d[v]+mp[v][i];
                if(!vis[i])
                {
                    q.push(i);
                    vis[i]=1;

                }

            }

        }


    }
    int ans=-1;
    for(i=1; i<=n; ++i)
        if(d[i]>ans)
            ans=d[i];


}


int main()
{
    for(int i=0; i<n; ++i)
        for(int j=0; j<n; ++j)
        {
            if(i!=j)
                mp[i][j]=INF;
            else
                mp[i][j]=0;
        }

    while(m--)
    {
        mp[i][j]=mp[j][i]=~~;
    }


    Spfa();

    return 0;
}


=============================================================


//Spfa 邻接表（推荐）


    struct node
{
    int v;
    int next;
    int cost;
} Edge,e[M];


//Insert
//无向图的spfa的边要存两遍

void addEdge()
{
    mp[cnt].v=to;
    mp[cnt].cost=cost;
    mp[cnt].next=headlist[from];
    headlist[from]=cnt++;
    mp[cnt].v=to;
    mp[cnt].cost=cost;
    mp[cnt].next=headlist[from];
    headlist[from]=cnt++;

}

//

void Spfa()
{
    int i,j;

    for(i=0; i<n; ++i)
    {
        d[i]=INF;
        vis[i]=0;

    }

    d[start]=0;
    vis[start]=1;
    queue<int>q;
    q.push(start);
    while(!q.empty())
    {
        int v==q.front();
        q.pop();
        vis[v]=0;
        for(i=headlist[v]; i!=-1; i=mp[i].next)
        {
            int b=mp[i].v;
            if(d[b]>d[v]+mp[i].cost)
            {
                d[b]=d[v]+mp[i].cost;
                if(!vis[b])
                {
                    vis[b]=1;
                    q.push(b);

                }
            }

        }



    }
    int ans=-1;
    for(i=1; i<n; ++i)
    {
        if(d[u]>ans)
            ans=d[i];

    }


}


int main()
{

    //for(i=1; i<=n; i++)
    //   headlist[i]=-1;
    memset(head,-1,sizeof(head));

    cnt=0;
    cin>>from>>to>>cost;
    // Insert(edge1,head1,u,v,w);
    // Insert(edge2,head2,v,u,w);

}



=============================================================

    Bellman_ford
// 这种算法比较少用，不多介绍了

//不断进行松弛操作 
    void bellman_ford()
{
    int i,j,start=1;
    for(i=1; i<=n; i++)
        d[i]=INF;

    d[start]=0;

    for (i=1; i<n; i++)
    {
        //重复进行n-1次收缩
        for (j=0; j<m; j++)
        {
            //对每条边进行收缩
            if (d[t[j].u]+t[j].w<d[t[j].v])
                d[t[j].v]=d[t[j].u]+t[j].w;
            //分别对每条边的两个顶点分别进行收缩
            if (d[t[j].v]+t[j].w<d[t[j].u])
                d[t[j].u]=d[t[j].v]+t[j].w;
        }
    }       //简单说就是不断进行松弛
    int ans=-1;
    for(i=2; i<=n; i++)
        if(d[i]>ans)
            ans=d[i];


}


int main()
{
    m=0;
    t[m].u=;
    t[m].v=;
    t[m].w=;
    m++;

}