1.Floyd
Floyd是先枚举转接点,从而达到更新最小值的目的。到后期好像O(n^3) 像闹着玩一样,但在一些n<=100的环境下还是很好用的。。。
1 inline void Floyd(int x){ 2 memset(dis,88,sizeof(dis)); 3 for(register int i=1,x,y;i<=m;++i){ 4 scanf("%d%d",&x,&y); 5 scanf("%d",dis[x][y]);dis[y][x]=dis[x][y]; 6 } 7 for(register int i=1;i<=n;++i) dis[i][i]=0; 8 for(register int k=1;k<=n;++k){ 9 for(register int i=1;in;++i){ 10 for(register int j=1;jn;++j){ 11 if(dis[i][k]+dis[k][j]<dis[i][j]) dis[i][j]=dis[i][k]+dis[k][j]; 12 } 13 } 14 } 15 }Floyd
2.Dijkstra
Dijkstra在图论问题中主要的优点是较稳定,不会被特殊设计的测试点卡掉,还可以记录路径(噩梦。。。)下面为堆优化的代码。
1 inline void dijkstra(int x) { 2 priority_queue<node> q; 3 q.push_back(node{0, s}); 4 for(register int i=1;i<=n;++i) dis[i]=100000000; 5 dis[x]=0; 6 memset(judge,0,sizeof(judge)); 7 while(!q.empty()){ 8 node xx=q.top(); q.pop(); 9 int to=xx.to; 10 if(judge[to]) continue;//如果这个点已经被提出过了,直接抛弃 (适用于那种松弛之后重复放入队列的点) 11 judge[to]=true; 12 for(register int i=0;i<q[to].size();++i){ 13 Edge& e = edges(q[to][i]); 14 if(e.dist+dis[to]<dis[e.to]&&dis[to]<100000000) { 15 dis[e.to]=e.dist+dis[to]; 16 p[e.to]=G[to][i]; //记录路径 17 q.push_back(Edge(dis[e.to], e.to));//把松弛过后点的d值重新放入队列 18 } 19 } 20 } 21 }Dijkstra
3.Spfa
Spfa是笔者比较青睐的算法。Spfa可以在压队的过程中判断是否存在环,还可以处理负环。
1 inline void Spfa(int x){ 2 queue<int> q; 3 memset(dis,88,sizeof(dis)); 4 memset(judge,0,sizeof(judge); 5 dis[x]=0; 6 q.push(x); 7 while(q.size()){ 8 int xx=q.front(); q.pop; 9 for(register int i=first[xx];i;i=a[i].next){ 10 int to=a[i].to; 11 if(dis[to]+a[i].w<dis[xx]){ 12 dis[xx]=dis[to]+a[i].w; 13 if(!judge[to]){ 14 q.push(to); judge[to]=1; 15 nums[y]++;//记录加入次数 16 if(nums[y]>n) return 0; 17 //如果这个点加入超过n次,说明存在负圈,直接返回 18 } 19 } 20 } 21 } 22 }Spfa