虽然时间复杂度都清楚，不过实际运行起来如何心里还是没底，实践才是检验真理的标准啊

 

前面在USACO 3.2.6 Sweet Butter 那道题中已经看到，稀疏图中对单源问题来说 SPFA 的效率略高于 Heap+Dijkstra ；对于无向图上的 APSP (All Pairs Shortest Paths)问题，SPFA算法加上优化后效率更是远高于 Heap+Dijkstra。今次再来看一看稠密图上的实验结果。

 

(注：以下提到的Dijkstra，如无特别说明，均指加入二叉堆(Binary-Heap)优化的Dijkstra算法，程序中由STL的优先队列(piority_queue)实现)

 

程序随机生成一个 N 顶点的无向完全图，之后分别用三种算法求所有顶点对之间的最短路径并统计各算法耗费的时间。程序代码附后

 

(1)不加优化
试验一：
Number of vertexes: 100

Floyd consumed:     0.070 secs
SPFA consumed:      0.240 secs
Dijkstra consumed:  0.040 secs

 

试验二：
Number of vertexes: 300

Floyd consumed:     0.911 secs
SPFA consumed:      2.183 secs
Dijkstra consumed:  0.891 secs

 

试验三：
Number of vertexes: 600

Floyd consumed:     6.719 secs
SPFA consumed:      19.709 secs
Dijkstra consumed:  6.589 secs

 

可以看到完全图果然是Floyd算法的老本行，写起来复杂得多的Heap+Dijkstra比起区区三行的Floyd并不具有太多优势；虽然没有写进程序，不过可以预见不加Heap的Dijkstra是肯定要败给Floyd的。
比起前两个，SPFA就不那么好过了，基本耗费了2-3倍的时间才完成计算，可见在稠密图的单源最短路径问题上SPFA比起Dijkstra确实有很大劣势。

 

(2)SPFA针对无向图的APSP问题加优化，优化方法见前面文章所述
试验四：
Number of vertexes: 100

Floyd consumed:     0.070 secs
SPFA consumed:      0.070 secs
Dijkstra consumed:  0.080 secs

 

试验五：
Number of vertexes: 300

Floyd consumed:     0.981 secs
SPFA consumed:      0.641 secs
Dijkstra consumed:  0.902 secs

 

试验六：
Number of vertexes: 600

Floyd consumed:     6.820 secs
SPFA consumed:      5.077 secs
Dijkstra consumed:  6.590 secs

 

SPFA加上优化后效率有了大幅提高，不但超过了Floyd，比起Dijkstra还略高20%左右。我不打算继续针对完全图的情况做任何优化，因为这里要比较的应该是对一般图都适用的普通算法。

 

总结一下：
(1)对于稀疏图，当然是SPFA的天下，不论是单源问题还是APSP问题，SPFA的效率都是最高的，写起来也比Dijkstra简单。对于无向图的APSP问题还可以加入优化使效率提高2倍以上。
(2)对于稠密图，就得分情况讨论了。单源问题明显还是Dijkstra的势力范围，效率比SPFA要高2-3倍。APSP问题，如果对时间要求不是那么严苛的话简简单单的Floyd即可满足要求，又快又不容易写错；否则就得使用Dijkstra或其他更高级的算法了。如果是无向图，则可以把Dijkstra扔掉了，加上优化的SPFA绝对是必然的选择。

 

 

OK，今天总算彻底弄清这仨的恩怨情仇，至少一段时间内不用再为选择哪个而头大了……

 

最后附上实验程序的代码：

#include<iostream>
#include<fstream>
#include<vector>
#include<cstdlib>
#include<ctime>
#include<queue>
using namespace std;

 

const int infinity=1000000000;

int N;
vector< vector<int> > vAdjMatrix;

vector< vector<int> > dijkstra;
vector< vector<int> > spfa;
vector< vector<int> > floyd;

 

inline bool relax(int u, int v, vector<int> &d){
    int nlen=d[u]+vAdjMatrix[u][v];
    if(nlen<d[v]){
        d[v]=nlen;
        return true;
    }
    return false;
}

 

void DoFloyd(){
    for(int i=0;i<N;++i)for(int j=0;j<N;++j)
        floyd[i][j]=vAdjMatrix[i][j];

 

    int newlen;
    for(int k=0;k<N;++k)
        for(int u=0;u<N;++u)
            for(int v=0;v<N;++v)
                if((newlen=floyd[u][k]+floyd[k][v])<floyd[u][v])
                    floyd[u][v]=floyd[v][u]=newlen;
}

 

void DoSPFA(){
    for(int iSource=0;iSource<N;++iSource){
        queue<int> Q;
        vector<bool> IsInQ(N,false);

 

        //optimizing begin:
        if(iSource>0){
            int iShort=0;
            for(int k=1;k<iSource;++k)if(spfa[k][iSource]<spfa[iShort][iSource])
                iShort=k;
            for(int iDes=0;iDes<N;++iDes)
                spfa[iSource][iDes]=spfa[iShort][iSource]+spfa[iShort][iDes];
        }
        //optimizing end.

 

        Q.push(iSource);
        IsInQ[iSource]=true;
        spfa[iSource][iSource]=0;

        while(!Q.empty()){
            int u=Q.front();
            Q.pop();
            IsInQ[u]=false;

            for(int v=0;v<N;++v)
                if(relax(u,v,spfa[iSource]) && !IsInQ[v]){
                    Q.push(v);
                    IsInQ[v]=true;
                }
        }
    }
}

 

void DoDijkstra(){
    struct ver_weight{
        int vertex;
        int weight;
        ver_weight(int Vertex, int Weight):vertex(Vertex),weight(Weight){}
        bool operator>(const ver_weight &comp)const{
            return weight>comp.weight;
        }
    };

 

    for(int iSource=0;iSource<N;++iSource){
        vector<bool> IsInset(N,false);
        int setcount=0;
        priority_queue< ver_weight,vector<ver_weight>,greater<ver_weight> > pq;

 

        IsInset[iSource]=true;
        ++setcount;
        for(int v=0;v<N;++v)if(vAdjMatrix[iSource][v]<infinity){
            dijkstra[iSource][v]=vAdjMatrix[iSource][v];
            pq.push(ver_weight(v,dijkstra[iSource][v]));
        }

        while(setcount<N){
            ver_weight uw=pq.top();
            pq.pop();
            if(IsInset[uw.vertex])continue;
            IsInset[uw.vertex]=true;
            ++setcount;
            for(int v=0;v<N;++v)if(relax(uw.vertex,v,dijkstra[iSource]))
                pq.push(ver_weight(v,dijkstra[iSource][v]));
        }
    }
}

 

int main(){
    ofstream fout("out.txt");
    cout<<"Input the number of vertexes: ";
    cin>>N;
    vAdjMatrix.resize(N,vector<int>(N,infinity));
    floyd.resize(N,vector<int>(N,infinity));
    spfa.resize(N,vector<int>(N,infinity));
    dijkstra.resize(N,vector<int>(N,infinity));

    fout<<"Number of vertexes: "<<N<<'\n'<<endl;

 

    //create the graph
    srand(unsigned(time(NULL)));
    for(int i=0;i<N;++i)for(int j=0;j<i;++j)
        vAdjMatrix[i][j]=vAdjMatrix[j][i]=rand();

    fout.precision(3);
    fout.setf(ios::fixed);
    clock_t start,finish;

 

    //floyd
    cout<<"Floyd start ... \n";
    start=clock();
    DoFloyd();
    finish=clock();
    cout<<"Floyd end.\n\n";
    fout<<"Floyd consumed:     "<<(double)(finish-start)/CLOCKS_PER_SEC<<" secs\n";

 

    //SPFA
    cout<<"SPFA start ... \n";
    start=clock();
    DoSPFA();
    finish=clock();
    cout<<"SPFA end.\n\n";
    fout<<"SPFA consumed:      "<<(double)(finish-start)/CLOCKS_PER_SEC<<" secs\n";

 

    for(int i=0;i<N;++i)for(int j=0;j<i;++j)
        if(floyd[i][j]!=spfa[i][j]){
            fout<<"SPFA worked wrong!\n";
            goto SPFA_end;   // try...catch are much better than goto...
        }

 

SPFA_end:

 

    //Dijkstra
    cout<<"Dijkstra start ... \n";
    start=clock();
    DoDijkstra();
    finish=clock();
    cout<<"Dijkstra end.\n";
    fout<<"Dijkstra consumed:  "<<(double)(finish-start)/CLOCKS_PER_SEC<<" secs\n";

 

    for(int i=0;i<N;++i)for(int j=0;j<i;++j)
        if(floyd[i][j]!=dijkstra[i][j]){
            fout<<"Dijkstra worked wrong!\n";
            goto Dijk_end;
        }

 

Dijk_end:

 

    //system("pause");
    return 0;
}

 

-------------------我--是--分--割--线------------------

好吧，既然有朋友提出来写个 naive 的 dijkstra 看看，我就也来比较一下

这里。

 

----------------PS.--------------------------------------

再补充，关于 SPFA 的两个优化 SLF 和 LLL:   懒得再写一篇了...

仍然拿随机生成的图做了实验，对单源问题，SLF 可使速度提高 15 ~ 20 %； SLF + LLL 可提高约 50 % (都是与纯SPFA相比)。

不过 LLL 写起来加的东西比较多一点，SLF 简单能加就随便加吧反正多一行而已

即便如此在稠密图上与 Heap + Dijkstra 相比仍有差距

 

对无向图 APSP 如果加上前述优化的话再加 SLF 或 LLL 反正略有提高，但不明显，最多好像也就 7~8 % 的样子，忘了。加不加无所谓。