Dijkstra算法(优先队列优化),O(ElogV),单源;
1 #include<stdio.h> 2 #include<string.h> 3 #include<queue> 4 using namespace std; 5 const int N=1100,M=11111; 6 int head[N],cnt; 7 int d[N],p[N]; 8 struct node 9 { 10 int v,w,next; 11 bool operator<(const node x)const 12 { 13 return x.w<w; 14 } 15 }e[M]; 16 void init() 17 { 18 cnt=0; 19 memset(head,-1,sizeof(head)); 20 } 21 void add(int u,int v,int w) 22 { 23 e[cnt].v=v,e[cnt].w=w; 24 e[cnt].next=head[u],head[u]=cnt++; 25 } 26 void dijstar(int s) 27 { 28 memset(d,0x3f,sizeof(d)); 29 memset(p,0,sizeof(p)); 30 priority_queue<node> q; 31 d[s]=0; 32 q.push(node{s,0,0}); 33 int i,u,v,w; 34 while(!q.empty()) 35 { 36 u=q.top().v; 37 q.pop(); 38 if(p[u]) continue; 39 p[u]=1; 40 for(i=head[u];i!=-1;i=e[i].next) 41 { 42 v=e[i].v,w=e[i].w; 43 if(!p[v]&&d[v]>d[u]+w) 44 { 45 d[v]=d[u]+w; 46 q.push(node{v,d[v],0}); 47 } 48 } 49 } 50 }
Spfa(基于Bellman-Ford)算法,单源。在实际的应用中SPFA的算法时间效率不是很稳定,为了避免最坏情况的出现,通常使用效率更加稳定的Dijkstra算法。
1 const int N=110; 2 const int M=N*N; 3 int d[N],p[N],cnt[N],q[M]; 4 int head[N],js;//,pre[N]; 5 struct node 6 { 7 int v,w,next; 8 }e[M]; 9 void add(int u,int v,int w) 10 { 11 e[js].v=v,e[js].w=w; 12 e[js].next=head[u],head[u]=js++; 13 } 14 void init() 15 { 16 //memset(pre,-1,sizeof(pre)); 17 memset(head,-1,sizeof(head)); 18 js=0; 19 } 20 int spfa(int s,int n) 21 { 22 memset(d,0x3f,sizeof(d)); 23 memset(p,0,sizeof(p)); 24 memset(cnt,0,sizeof(cnt)); 25 int u,v,w,l=0,r=0; 26 q[++r]=s,d[s]=0,p[s]=1; 27 while(l<r) 28 { 29 p[u=q[++l]]=0; 30 for(int i=head[u];i!=-1;i=e[i].next) 31 { 32 v=e[i].v,w=e[i].w; 33 if(d[v]>d[u]+w) 34 { 35 d[v]=d[u]+w; 36 //pre[v]=u; 37 if(!p[v]) 38 { 39 if(++cnt[v]>n) //存在负环 40 return 0; 41 p[v]=1; 42 q[++r]=v; 43 } 44 } 45 } 46 } 47 return 1; 48 } 49 void prpath(int s,int t) 50 { 51 int js=0,tmp[N]; 52 while(t!=s) 53 { 54 tmp[++js]=t; 55 t=pre[t]; 56 } 57 for(int i=js;i>=1;i--) 58 printf("%d->",tmp[i]); 59 printf("%d ",s); 60 }
Floyd算法,全源。d[i][i]实际上表示「从顶点 i 绕一圈再回来的最短路径」,因此图存在负环当且仅当 d[i][i]<0。
1 int d[N][N],path[N[N],n;//path记录路径,d表示初始距离(若相连则初始化为边权,若无则为无穷大) 2 int floyd() 3 { 4 int i,j,k; 5 for(i=1;i<=n;i++) 6 for(j=1;j<=n;j++) 7 path[i][j]=j; 8 for(k=1;k<=n;k++) 9 { 10 for(i=1;i<=n;i++) 11 { 12 for(j=1;j<=n;j++) 13 { 14 if(d[i][k]+d[k][j]<d[i][j]) 15 { 16 d[i][j]=d[i][k]+d[k][j]; 17 path[i][j]=path[i][k]; 18 if(i==j&&d[i][j]<0) ////存在负环 19 return 0; 20 } 21 } 22 } 23 } 24 return 1; 25 } 26 void prpath(int u,int v) 27 { 28 printf("%d->%d: ",u,v); 29 printf("%d",u); 30 while(u!=v) 31 { 32 printf("->%d",path[u][v]); 33 u=path[u][v]; 34 } 35 printf(" "); 36 }