在图论中，最短路算法是常见的。对于常见的几种算法，到底哪种更优，还是各有千秋？我们不妨一试。以下实验在1号机上进行，均为试验20次随机数取平均值的结果。
1.单源最短路径——dijkstra算法 void dijkstra() { int i,j,min=0; for(i=0;i for(j=0;j if(!use[j]&&d[i][j] if(dis[min]+d[min][j] 随机数产生器： for(i=0;i for(j=0;j d[i][j]=rand(); 当MAX=2000时（即点数为2000个），运行时间：28.2ms。当MAX更大时，内存会使用过多，故在1s时限内至多运行规模为2000的单源最短路径35次。 2.单源最短路径——Ford算法 int ford() { int i,j; for(i=1;i if(d[f[j]]+w[j] ①数据构造：10*n条随机边。当n=1000时，运行时间：49.95ms。当n=10000时，运行时间：6766ms。②数据构造：n*n条边的完全图。当n=1000时，运行时间6469ms。比Dijkstra和SPFA都慢很多，因为其算法的理论时间复杂度就达到了O(VE)，属于介于O(n^2)与O(n^3)的算法。但我们仍然需要这种算法，因为当图中存在负权时，必须使用Ford算法。同时，该算法还能判断图中是否存在负权回路（无解）。 3.单源最短路径——SPFA算法 struct mising{ int num; int poo; struct mising *p; }; int wor[500000]; int dis[60001]; int yes[60001]={0}; int beg=0,end=1; main() { int n,m; int a,b,c,i; struct mising q[60001],*qq[60001],*x; double s,t; FILE *fp; fp=fopen(\ fscanf(fp,\ for(i=0;i fscanf(fp,\ a--; b--; qq[a]->p=(struct mising *)malloc(sizeof(struct mising)); qq[b]->p=(struct mising *)malloc(sizeof(struct mising)); qq[a]=qq[a]->p; qq[b]=qq[b]->p; qq[a]->poo=b; qq[b]->poo=a; qq[a]->num=qq[b]->num=c; } s=clock(); for(i=0;i qq[i]->p=NULL; dis[i]=-1; } yes[0]=1; wor[0]=0; dis[0]=0; while(beg!=end) { x=q[wor[beg]].p; while(x!=NULL) { if(dis[x->poo]==-1||(dis[x->poo]>x->num+dis[wor[beg]]&&dis[x->poo]!=-1)) { dis[x->poo]=dis[wor[beg]]+x->num; wor[end]=x->poo; if(yes[x->poo]==0) { yes[x->poo]=1; end++; } } x=x->p; } yes[wor[beg]]=0; beg++; } printf(\ t=clock(); 随机数生成模块： fprintf(fp,\ for(i=0;i<10*n;i++) { j=rand()%n+1; k=rand()%n+1; while(j==k){ j=rand()%n+1; k=rand()%n+1;} fprintf(fp,\ } 运行时间（不含文件操作）：当n=100000时，运行时间1937ms；当n=10000时，运行时间141ms；当n=1000时，运行时间小于10ms。特别需要注意的是，当n=50000时，用时828ms，再加上文件操作用时，可称为是SPFA算法数据规模的上限。这组数据是n个点，10*n条随机边的情况下作出的。若使用O(n^2)的Dijkstra算法，时间将大幅增加。 对于单源最短路径，要考虑题意要求，稀疏图使用SPFA，密集图使用Dijkstra，以提高运行效率。 3.点对点最短路径——Floyed算法 void floyed() { int i,j,k,min=0; for(k=0;k if(d[i][k]+d[k][j] 当MAX=500时，运行时间：979.85ms。这提示我们，点对点最短路径的规模最大为500，否则会超时。 若使用MAX-1次dijkstra算法 void dijkstra() { int i,j,k,min=0; for(k=0;k for(j=0;j if(!use[j]&&d[i][j] if(dis[min]+d[min][j] 当MAX=500时，运行时间：1625ms，与floyed的980ms相比，显然慢了很多。因此，floyed算法是点对点最短路径的“正统”算法。 三、字符串匹配算法的比较 1.朴素匹配算法 for(i=0;i<1000;i++) S[i]=1; for(j=0;j<100000;j++) T[j]=1; s=clock(); tot=0; ls=strlen(S); lt=strlen(T); for(i=0;i printf(\ t=clock(); 运行时间：335.35ms。这组测试数据是：原串100000个1，匹配串1000个1. 若使用更极端的数据，如匹配串10000个1，则需要数秒出解，显然过慢。对于随机数据，由于匹配的可能性极小，用时很快是必然的。我们只考虑极端数据。 2.KMP算法（优化） int KMP() { int i,q=0; for(i=1;i<=ls;i++) { while(q>0&&T[q+1]!=S[i]) q=next[q]; if(T[q+1]==S[i]) q++; if(q==lt) a[tot++]=i-lt+1; } } void ff() { int q,k; for(q=1;q<=lt;q++) { k=next[q]; while(k>0&&T[k+1]==T[q+1]) k=next[k]; next[q]=k; } } void f() { int q,k; next[1]=0;k=0; for(q=2;q<=lt;q++) {while(k>0&&T[k+1]!=T[q]) k=next[k]; if(T[k+1]==T[q]) k=k+1; next[q]=k; } } 调用过程： f(); ff(); KMP(); 算法说明：函数f计算初始“回复位置”，函数ff计算优化后的“回复位置”，函数KMP