Single-source shortest path problem: SPFA vs. Dijkstra

Use USACO [3_2_butter] as an example

SPFA is an improvement of the Bellman-Ford algorithm, check the corresponding wikipedia page

1. worst case: same complexity as Bellman-Ford O(VE)

average performance: O(E), or O(kE) where k is about 2

2. able to handle negative-weight edges

3. two optimization techniques: SLF & LLL

graph storage: adjacent list + weight matrix

algorithm and result:

(1) SPFA (STL queue, no optimization)

Test 1: TEST OK [0.011 secs, 8348 KB]
   Test 2: TEST OK [0.000 secs, 8348 KB]
   Test 3: TEST OK [0.011 secs, 8348 KB]
   Test 4: TEST OK [0.011 secs, 8348 KB]
   Test 5: TEST OK [0.011 secs, 8348 KB]
   Test 6: TEST OK [0.032 secs, 8348 KB]
   Test 7: TEST OK [0.076 secs, 8348 KB]
   Test 8: TEST OK [0.119 secs, 8348 KB]
   Test 9: TEST OK [0.184 secs, 8348 KB]
   Test 10: TEST OK [0.184 secs, 8348 KB]
           

(2) Dijkstra + STL priority queue

Test 1: TEST OK [0.000 secs, 8348 KB]
   Test 2: TEST OK [0.000 secs, 8348 KB]
   Test 3: TEST OK [0.011 secs, 8348 KB]
   Test 4: TEST OK [0.011 secs, 8348 KB]
   Test 5: TEST OK [0.022 secs, 8348 KB]
   Test 6: TEST OK [0.065 secs, 8348 KB]
   Test 7: TEST OK [0.119 secs, 8348 KB]
   Test 8: TEST OK [0.227 secs, 8348 KB]
   Test 9: TEST OK [0.389 secs, 8348 KB]
   Test 10: TEST OK [0.367 secs, 8348 KB]
           

source  code:

(1) Dijkstra

#include <cstdio>
#include <climits>
#include <queue>

using namespace std;

int g[800][800],adjlst[800][800],deg[800];

int main()
{
        freopen("butter.in","r",stdin);
        freopen("butter.out","w",stdout);
        int c,n,m,a[500],b[800]={0};
        scanf("%d%d%d",&c,&n,&m);
        for(int i=0;i<c;i++)
        {
                scanf("%d",&a[i]);
                a[i]--;
                b[a[i]]++;
        }
        for(int i=0;i<n;i++)
                for(int j=0;j<n;j++)
                        g[i][j]=1000000;
        for(int i=0;i<m;i++)
        {
                int s,t,w;
                scanf("%d%d%d",&s,&t,&w);
                s--,t--;
                g[s][t]=g[t][s]=w;
                adjlst[s][deg[s]++]=t;
                adjlst[t][deg[t]++]=s;
        }
        for(int i=0;i<n;i++)
                g[i][i]=0;
        int ans=INT_MAX,sum;
        for(int i=0;i<n;i++)
        {
                int cnt=b[i];
                bool vst[800]={0};
                vst[i]=1;
                int dst[800];
                priority_queue<pair<int,int>,vector<pair<int,int> >,greater<pair<int,int> > > q;
                for(int j=0;j<n;j++)
                {
                        dst[j]=g[i][j];
                        q.push(make_pair(dst[j],j));
                }
                while(cnt<c)
                {
                        int mindst=q.top().first,idx=q.top().second;
                        q.pop();
                        if(vst[idx])
                                continue;
                        if(mindst>=INT_MAX)
                                break;
                        vst[idx]=1;
                        cnt+=b[idx];
                        for(int j=0;j<deg[idx];j++)
                                if(!vst[adjlst[idx][j]] && dst[adjlst[idx][j]]>mindst+g[idx][adjlst[idx][j]])
                                {
                                        dst[adjlst[idx][j]]=mindst+g[idx][adjlst[idx][j]];
                                        q.push(make_pair(dst[adjlst[idx][j]],adjlst[idx][j]));
                                }
                }
                if(cnt<c)
                        continue;
                sum=0;
                for(int i=0;i<c;i++)
                        sum+=dst[a[i]];
                if(sum<ans)
                        ans=sum;
        }
        printf("%d\n",ans);
        return 0;
}
           

(2) SPFA

#include <cstdio>
#include <climits>
#include <queue>

using namespace std;

int g[800][800],adjlst[800][800],deg[800];

int main()
{
        freopen("butter.in","r",stdin);
        freopen("butter.out","w",stdout);
        int c,n,m,a[500],b[800]={0};
        scanf("%d%d%d",&c,&n,&m);
        for(int i=0;i<c;i++)
        {
                scanf("%d",&a[i]);
                a[i]--;
                b[a[i]]++;
        }
        for(int i=0;i<n;i++)
                for(int j=0;j<n;j++)
                        g[i][j]=1000000;
        for(int i=0;i<m;i++)
        {
                int s,t,w;
                scanf("%d%d%d",&s,&t,&w);
                s--,t--;
                g[s][t]=g[t][s]=w;
                adjlst[s][deg[s]++]=t;
                adjlst[t][deg[t]++]=s;
        }
        for(int i=0;i<n;i++)
                g[i][i]=0;
        int ans=INT_MAX;
        for(int i=0;i<n;i++)
        {
		int dst[800];
		for(int j=0;j<n;j++)
			dst[j]=INT_MAX;
		dst[i]=0;
		queue<int> q;
		q.push(i);
		bool inq[800]={0};
		inq[i]=1;
		while(!q.empty())
		{
			int u=q.front();
			q.pop();
			for(int j=0;j<deg[u];j++)
			{
				int v=adjlst[u][j];
				if(dst[u]+g[u][v]<dst[v])
				{
					dst[v]=dst[u]+g[u][v];
					if(!inq[v])
						q.push(v);
				}
			}
		}
                int sum=0;
                for(int i=0;i<c;i++)
                        sum+=dst[a[i]];
                if(sum<ans)
                        ans=sum;
        }
        printf("%d\n",ans);
	return 0;
}