首页 > 代码库 > vijos1635 SPFA和FLOYD算法如何打印路径

vijos1635 SPFA和FLOYD算法如何打印路径

2024-07-17 03:58:06   222人阅读

 

之前打的spfa或是floyd都只是用来求最短路，对于如何打印路径问题一点都没有概念

可能也是因为对于原理没有很理解的缘故？

总之，之后赶紧看了一下，现在总算是明白了.....MARK一下自己的理解

 

早晨碰到了一题挺裸的最短路问题：vijos1635

1.首先说说spfa的方法：

其实自己之前打的最多的spfa是在网格上的那种，也就是二维的

一维的需要邻接表+queue

以及对于queue的操作，自己也是醉了

 

这里贴一个模板（不含打印路径）：

#include<cstdio>#include<cstring>#include<queue>#include<iostream>using namespace std;const int maxn=10100;int n,m,k,t,x,y,s,ans=0;long long tot=0;struct edge{	int from,to,w,next;}e[10100000];int head[maxn],dist[maxn];bool vis[maxn];void add(int x,int y,int z){//邻接表	e[tot].from=x;	e[tot].to=y;	e[tot].w=z;	e[tot].next=head[x];	head[x]=tot++;}void spfa(int s){	queue<int>q;	memset(dist,63,sizeof(dist));	memset(vis,false,sizeof(vis));//感觉这里的赋值和二维的略有区别，这里是初始值false	q.push(s);	dist[s]=0;	while(!q.empty()){		int u=q.front();		q.pop();		vis[u]=false;②		for(int i=head[u];i!=-1;i=e[i].next){			int v=e[i].to;			if(dist[v]>dist[u]+e[i].w){				dist[v]=dist[u]+e[i].w;				if(!vis[v]){         //如果已经入队,或是初始值①					vis[v]=true;					q.push(v);				}			}		}	}}int main(){	scanf("%d",&n);	memset(head,-1,sizeof(head));//记得head赋值为-1	for(int i=1;i<=n;i++)	   for(int j=1;j<=n;j++){	   	  scanf("%d",&s);	   	  if(s!=0){	   	  	  add(i,j,s);	   	  }	   }    spfa(1);    printf("%d",dist[n]);    return 0;}

 好好感受一下①和②

 

对于spfa打印路径问题：

这里就需要用上指针的思想，去找n的前驱

所以如果dist有更新值，那么就记录下，但是这里要理解，

你记录的并不是根据这条路的路径顺序记的

说白了就是，f[1]并不是第一条路径

而是让v->u，这才是f应该做的

 

   if(dist[v]>dist[u]+e[i].w){	dist[v]=dist[u]+e[i].w;
	f[v]=u;//在更新值的后面加上这个
	if(!vis[v]){	vis[v]=true;	q.push(v);	}
  }

 以及调用一个递归函数寻找前驱：

void printpath(int k){    if(k!=0){    	printpath(f[k]);    	printf("%d ",k);    }}

 

2.FLOYD算法：

也是在更新值后面加上一条语句：

k=1-n

i=1-n

j=1-n

  if(..>..)

    dist[i][j]=dist[i][k]+dist[k][j];

    f[i][j]=f[i][k];

 

 for(v=0; v<n; ++v)     {         for(w=v+1; w<n; w++)         {            printf("%d ->%d:%d ",v,w,D[v][w]);            k=P[v][w];                /* 获得第一个路径顶点下标 */            printf(" path: %d",v);    /* 打印源点 */            while(k!=w)                /* 如果路径顶点下标不是终点 */            {                printf(" -> %d",k);    /* 打印路径顶点 */                k=P[k][w];            /* 获得下一个路径顶点下标 */            }            printf(" -> %d\n",w);    /* 打印终点 */        }        printf("\n");    }

 


联系
我们