转载请注明出处:http://blog.csdn.net/wangjian8006
dijkstra算法:
首先他的思想是按路径长度递增次序产生最短路径算法,将d[i]看成从1到i的最短路径,那么如果v是i的邻边的话有d[i]=min(d[i],d[v]+map[v][i]),并且这个算法只能求单源非负权值最短路径
void dijstra(){ int i,j,ans=-1,min,v; int d[MAXV],vis[MAXV]; //d数组表示从原点到i点的最短距离 //vis用于表达这个点是否已经被选中 for(i=1;i<=n;i++){ d[i]=INF; vis[i]=0; } d[start]=0; //因为start到start的距离为0 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] && d[v]+map[v][j]<d[j]) d[j]=d[v]+map[v][j]; } }
bellman_ford算法:
求含负权图的单源最短路径算法,效率很低,但代码很容易写。即进行不停地松弛(原文是这么写的,为什么要叫松弛,争议很大),每次松弛把每条边都更新一下,若n-1次松弛后还能更新,则说明图中有负环,无法得出结果,否则就成功完成。
struct { int s,e,w; }t[MAXE]; void bellman_ford(){ int i,j,ans=-1,start=1; int d[MAXV]; 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].s]+t[j].w<d[t[j].e]) d[t[j].e]=d[t[j].s]+t[j].w; //分别对每条边的两个顶点分别进行收缩 if (d[t[j].e]+t[j].w<d[t[j].s]) d[t[j].s]=d[t[j].e]+t[j].w; } } } /*bellman_ford加个flag优化:*/ void bellman_ford(){ int i,j,ans=-1,start=1; int d[MAXV]; for(i=1;i<=n;i++) d[i]=INF; d[start]=0; int flag=1; while(flag){ flag=0; //松弛到没有再更新的就退出 for (j=0;j<m;j++){ //对每条边进行收缩 if (d[t[j].s]+t[j].w<d[t[j].e]) {d[t[j].e]=d[t[j].s]+t[j].w;flag=1;} //分别对每条边的两个顶点分别进行收缩 if (d[t[j].e]+t[j].w<d[t[j].s]) {d[t[j].s]=d[t[j].e]+t[j].w;flag=1;} } } }
spfa算法:spfa实际上是bellman_ford算法的优化,是一个国产算法求最短路径的,同样适合含负权图
SPFA算法有两个优化算法 SLF 和 LLL:
SLF:Small Label First 策略,设要加入的节点是j,队首元素为i,若dist(j)<dist(i),则将j插入队首,否则插入队尾。
LLL:Large Label Last 策略,设队首元素为i,队列中所有dist值的平均值为x,若dist(i)>x则将i插入到队尾,查找下一元素,直到找到某一i使得dist(i)<=x,则将i出对进行松弛操作。
SLF 可使速度提高 15 ~ 20%;SLF + LLL 可提高约 50%。在实际的应用中SPFA的算法时间效率不是很稳定,为了避免最坏情况的出现,通常使用效率更加稳定的Dijkstra算法。
/*spfa邻接表*/ struct { int s,e,w,next; }t[MAXE]; int n,m,headlist[MAXV]; void main(){ for(i=1;i<=n;i++) headlist[i]=-1; for(i=2;i<=n;i++) for(j=1;j<i;j++){ scanf("%d",s); //无向图的spfa的边要存两遍 t[m].w=s; t[m].s=i; t[m].e=j; t[m].next=headlist[j]; headlist[j]=m++; t[m].w=s; t[m].s=j; t[m].e=i; t[m].next=headlist[i]; headlist[i]=m++; } } void spfa(){ int i,ans=-1,start=1,v,b; int d[MAXV],vis[MAXV]; queue <int>q; for(i=1;i<=n;i++){ d[i]=INF; vis[i]=0; } d[start]=0; vis[start]=1; q.push(start); while(!q.empty()){ v=q.front(); q.pop(); vis[v]=0; for(i=headlist[v];i!=-1;i=t[i].next){ b=t[i].s; if(d[v]+t[i].w<d[b]){ d[b]=d[v] + t[i].w; if(!vis[b]){ vis[b]=1; q.push(b); } } } } } /*spfa邻接矩阵:*/ void spfa(){ int i,j,ans=-1,v,start=1; int d[MAXV],vis[MAXV]; queue <int>q; for(i=1;i<=n;i++){ d[i]=INF; vis[i]=0; } q.push(start); d[start]=0; vis[start]=1; while(!q.empty()){ v=q.front(); q.pop(); vis[v]=0; for(i=1;i<=n;i++){ if(d[i]>d[v]+map[v][i]){ d[i]=d[v]+map[v][i]; if(!vis[i]){ q.push(i); vis[i]=1; } } } } }
floyd算法:
Floyd算法又称为弗洛伊德算法,插点法,是一种用于寻找给定的加权图中顶点间最短路径的算法
采用的是(松弛技术),对在i和j之间的所有其他点进行一次松弛。所以时间复杂度为O(n^3);
其状态转移方程如下: map[i,j]:=min{map[i,k]+map[k,j],map[i,j]}
void floyd(){ int i,j,k; for(k=1;k<=n;k++) for(i=1;i<=n;i++) for(j=1;j<=n;j++) if(map[i][k]+map[k][j]<map[i][j]) map[i][j]=map[i][k]+map[k][j]; }