Bellman Ford+SPFA队列优化（路径还原输出最短路的路径）

迷南。 2022-09-24 14:17 151阅读 0赞

### ——————有向图—————— ###

### ![20160802091610993][]    ###

## ①邻接表（效率较高） ##

#include <iostream>
    #include <cstdio>
    #include <cstring>
    #include <cmath>
    #include <vector>
    #include <queue>
    #include <map>
    #include <algorithm>
    using namespace std;
    #define INF 0xfffffff
    #define MAXN 1010
    
    struct Edge
    {
        int u,v,w;
    };
    Edge edge[MAXN];//邻接表
    int n,m;//顶点数和边数
    int dist[MAXN];//顶点s到其他顶点的最短路径、
    int path[MAXN];//path[i]表示v0到vi的最短路径上vi的前一个顶点的序号
    int shortest[MAXN];//输出最短路径上的各个顶点时存放的各个顶点的序号
    
    void Bellman(int s)//顶点s到其他顶点的最短路径
    {
        int i,j;
        for(i=0; i<n; ++i)//初始化
        {
            dist[i]=INF;
            path[i]=-1;
        }
        dist[s]=0;
        for(i=1; i<n; ++i)
            for(j=0; j<m; ++j)
            {
                Edge e=edge[j];
                if(dist[e.u]!=INF&&e.w+dist[e.u]<dist[e.v])//顶点k到j有直接路径而且途径k可以使得路径缩短
                {
                    dist[e.v]=e.w+dist[e.u];
                    path[e.v]=e.u;
                }
            }
    }
    
    int main()
    {
        ios::sync_with_stdio(false);
        cin.tie(0);
        int i,j;
        cin>>n>>m;
        for(i=0; i<m; ++i)
            cin>>edge[i].u>>edge[i].v>>edge[i].w;
        Bellman(0);//顶点0到其他顶点的最短路
        for(i=1; i<n; ++i)//依次输出每个顶点最短路的路径节点
        {
            cout<<dist[i]<<'\t';//最短路
            memset(shortest,0,sizeof(shortest));
            int k=0;
            shortest[k]=i;
            while(path[shortest[k]]!=0)//倒向追踪
            {
                ++k;
                shortest[k]=path[shortest[k-1]];
            }
            ++k;
            shortest[k]=0;
            for(j=k; j>0; --j)//路径输出
                cout<<shortest[j]<<"→";
            cout<<shortest[0]<<endl;
        }
        return 0;
    }
    /**
    7 10
    0 1 6
    0 2 5
    0 3 5
    1 4 -1
    2 1 -2
    2 4 1
    3 2 -2
    3 5 -1
    4 6 3
    5 6 3
    **/

## ②邻接矩阵 ##

#include <iostream>
    #include <cstdio>
    #include <cstring>
    #include <cmath>
    #include <vector>
    #include <queue>
    #include <map>
    #include <algorithm>
    using namespace std;
    #define INF 0xfffffff
    #define MAXN 1010
    
    int n,m;//顶点数和边数
    int edge[MAXN][MAXN];//邻接矩阵
    int dist[MAXN];//顶点s到其他顶点的最短路径、
    int path[MAXN];//path[i]表示v0到vi的最短路径上vi的前一个顶点的序号
    int shortest[MAXN];//输出最短路径上的各个顶点时存放的各个顶点的序号
    
    void Bellman(int s)//顶点s到其他顶点的最短路径
    {
        int i,j,k;
        for(i=0; i<n; ++i)//初始化
        {
            dist[i]=edge[s][i];
            if(i!=s&&dist[i]<INF)
                path[i]=s;
            else path[i]=-1;
        }
        for(i=2; i<n; ++i)
            for(j=0; j<n; ++j)
                if(j!=s)
                {
                    for(k=0; k<n; ++k)
                        if(edge[k][j]<INF&&dist[k]+edge[k][j]<dist[j])//顶点k到j有直接路径而且途径k可以使得路径缩短
                        {
                            dist[j]=dist[k]+edge[k][j];
                            path[j]=k;
                        }
                }
    }
    
    int main()
    {
        ios::sync_with_stdio(false);
        cin.tie(0);
        int i,j,u,v,w;
        cin>>n>>m;
        for(i=0; i<n; ++i)//初始化
            for(j=0; j<n; ++j)
            {
                if(i==j) edge[i][j]=0;
                else edge[i][j]=INF;
            }
        for(i=0; i<m; ++i)
        {
            cin>>u>>v>>w;
            edge[u][v]=w;
        }
        Bellman(0);//顶点0到其他顶点的最短路
        for(i=1; i<n; ++i)//依次输出每个顶点最短路的路径节点
        {
            cout<<dist[i]<<'\t';//最短路
            memset(shortest,0,sizeof(shortest));
            int k=0;
            shortest[k]=i;
            while(path[shortest[k]]!=0)//倒向追踪
            {
                ++k;
                shortest[k]=path[shortest[k-1]];
            }
            ++k;
            shortest[k]=0;
            for(j=k; j>0; --j)//路径输出
                cout<<shortest[j]<<"→";
            cout<<shortest[0]<<endl;
        }
        return 0;
    }
    /**
    7 10
    0 1 6
    0 2 5
    0 3 5
    1 4 -1
    2 1 -2
    2 4 1
    3 2 -2
    3 5 -1
    4 6 3
    5 6 3
    **/

## ③SPFA队列优化 ##

#include <iostream>
    #include <cstdio>
    #include <cstring>
    #include <vector>
    #include <queue>
    #include <iomanip>
    #include <algorithm>
    #define MAXN 10010
    #define INF 0xfffffff
    using namespace std;
    
    struct ArcNode
    {
        int to;
        int weight;
        ArcNode *next;
    };
    queue<int> Q;//队列中的节点为顶点序号
    int n;//顶点个数
    ArcNode * List[MAXN];//每个顶点的边链表表头指针
    int inq[MAXN];//每个顶点是否在队列中的标志
    int dist[MAXN],path[MAXN];
    void SPFA(int src)
    {
        int i,u;//u为队列头顶点序号
        ArcNode * temp;
        for(i=0; i<n; ++i)//初始化
        {
            dist[i]=INF;
            path[i]=src;
            inq[i]=0;
        }
        dist[src]=0;
        path[i]=src;
        ++inq[src];
        Q.push(src);
        while(!Q.empty())
        {
            u=Q.front();
            Q.pop();
            --inq[u];
            temp=List[u];
            while(temp!=NULL)
            {
                int v=temp->to;
                if(dist[v]>dist[u]+temp->weight)
                {
                    dist[v]=dist[u]+temp->weight;
                    path[v]=u;
                    if(!inq[v])
                    {
                        Q.push(v);
                        ++inq[v];
                    }
                    temp=temp->next;
                }
            }
        }
    }
    int main()
    {
        int i,j;
        int u,v,w;
        cin>>n;
        memset(List,0,sizeof(List));
        ArcNode *temp;
        while(cin>>u>>v>>w)
        {
            temp=new ArcNode;
            temp->to=v;//构造邻接表
            temp->weight=w;
            temp->next=NULL;
            if(List[u]==NULL) List[u]=temp;
            else
            {
                temp->next=List[u];
                List[u]=temp;
            }
        }
        SPFA(0);//求顶点0到其他顶点的最短路径
        for(j=0; j<n; ++j)//释放边链表上各边结点所占用的存储空间
        {
            temp=List[j];
            while(temp!=NULL)
            {
                List[j]=temp->next;
                delete temp;
                temp=List[j];
            }
        }
        int shortest[MAXN];//输出最短路径上的各个顶点时存放各个顶点的序号
        for(i=1; i<n; ++i)
        {
            cout<<dist[i]<<'\t';//输出顶点0到顶点i的最短路径长度
            memset(shortest,0,sizeof(shortest));
            int k=0;
            shortest[k]=i;
            while(path[shortest[k]]!=0)
            {
                ++k;
                shortest[k]=path[shortest[k-1]];
            }
            ++k;
            shortest[k]=0;
            for(j=k; j>0; --j)
                cout<<shortest[j]<<"->";
            cout<<shortest[0]<<endl;
        }
        return 0;
    }
    /*
    7
    0 1 6
    0 2 5
    0 3 5
    1 4 -1
    2 1 -2
    2 4 1
    3 2 -2
    3 5 -1
    4 6 3
    5 6 3
    */

![20160807174932946][]

[20160802091610993]: /images/20220719/22c728ca5fbe4ab4afb320f06b983700.png
[20160807174932946]: /images/20220719/e25aca9b12e14b93bbb8a58c66576eea.png